最近公司要做一個(gè)抽獎(jiǎng)系統(tǒng)，抽獎(jiǎng)源數(shù)據(jù)量不到1000（數(shù)據(jù)包括姓名、手機(jī)號(hào)、所屬部門）。共5個(gè)獎(jiǎng)項(xiàng)，每一獎(jiǎng)項(xiàng)至少5人，可能還有特等獎(jiǎng)，當(dāng)然這些都是已知的。我現(xiàn)在想到的是，一次性取出所有數(shù)據(jù)的唯一ID，然后抽每一個(gè)獎(jiǎng)項(xiàng)的每一個(gè)人都隨機(jī)一次（這樣應(yīng)該更公平吧？），抽完一次后更新已經(jīng)抽出的人的狀態(tài)，取出數(shù)據(jù)展現(xiàn)，接著繼續(xù)。問：1、總感覺這樣的算法不太合適，是否有更好的算法？2、像新浪微博的轉(zhuǎn)發(fā)抽獎(jiǎng)系統(tǒng)，數(shù)據(jù)量可能幾十萬到幾百萬，顯然上面的算法是不合適的，不知道是怎么樣一種算法？
1 回答
慕的地8271018
TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超4個(gè)贊
1. 你的需求其實(shí)很簡(jiǎn)單，就是從N個(gè)元素中隨機(jī)抽取k個(gè)，并且要盡量保證每個(gè)元素被抽中的概率都是k/N。最簡(jiǎn)單的辦法就是將這N個(gè)元素存在一個(gè)數(shù)組中，隨機(jī)打亂（保證每個(gè)元素出現(xiàn)在每個(gè)位置的概率都相同），然后選取前k個(gè)就行。具體的算法，直接用stl algorithm里的random_shuffle
2. 對(duì)于微博這種轉(zhuǎn)發(fā)抽獎(jiǎng)系統(tǒng)，其難度在于
(1) N很大
(2) N未知
如果是在活動(dòng)結(jié)束后才給出所有中獎(jiǎng)結(jié)果，那么就可以采用一種叫做“蓄水池抽樣”的算法，時(shí)間復(fù)雜度O(N)（掃一遍），空間復(fù)雜度O(k)，從數(shù)學(xué)上可以保證（只要隨機(jī)數(shù)發(fā)生器是真隨機(jī)），每一個(gè)元素中獎(jiǎng)的概率是 k/N。
添加回答
舉報(bào)
0/150
提交
取消