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