一道關于随機算法的面試題(轉)

今天碰到了一道面試題：原題大緻是，每首歌曲都是一個評分，現在有2000首歌曲，要求實作一個随機播放器，每首歌曲播放的機率應該正比于它的評分，例如評分9.1的歌曲，和評分7.9的歌曲，播放的次數應該是91：79。

面試官給的答案是大緻如此：

先把評分從小到大排序，之後把根據每首歌的評分，生成一個半閉開區間，然後生成一個随機數，看随機數落在哪個區間，就是選擇的那首歌。例如，有三首歌，評分是[1,2,3] 那麼應該是生成三個區間 [0-1,1-3,3-6]，之後生成一個0-6之間的随機數，随機數落在哪個區間，就選擇對應的歌曲。考慮排序的效率，這是一個nLogn的算法。

但是，這個算法是有纰漏的，沒有考慮到評分重複的情況，如果三首歌的評分是[1,2,2]，那麼應該是生成兩個區間[0-1,1-5], 如果落在第二個區間，還需要從兩首評分為2的歌曲裡面随機選出一首來。這樣的話，實作起來就相當複雜了。

最後，如果照上面那樣考慮，就完整了，但是實作起來的話，會發現，沒有很好的資料結構能判斷哪個随機數是落在哪個區間的，除非周遊所有的區間。

那麼，優雅又高效的解法是什麼樣的，假定每個評分隻到小數點後一位，那麼其實，利用空間換取時間的思路，隻需要把每首歌按照他的評分多少相應的複制多少重複的歌曲，并且把所有的歌曲都扔到一個池子裡面，之後從池子裡面等機率的選取一首歌就行了。在最壞的情況下，2000首歌曲的評分都是9.9，那麼每首歌需要複制99首，空間效率是On，時間複雜度為O1

算法的scala實作如下:

測試

結果

ps：我是回家路上才想起這種解法的，我和我老婆說，化學系畢業的她直接就給出了正确的解法，哎，被數學學霸碾壓的滋味就是這麼銷魂。

更新：早上和V站的V友讨論以後，發現面試官說的那種映射是可以實作的，例如有三首歌,評分是[1,2,3]那麼區間段是[0-1,2-4,4-6]這個時候，隻需要存一個數組[1,4,6],之後用2分查找就能得出正确的結論了，當然還需要考慮評分重複的情況。

rangeMap guava中有現成的實作，我還是太年輕啊。此外，這種權重随機的算法，早有研究

http://www.electricmonk.nl/Writings/HomePage?action=download&upname=weighted_random_dist.pdf

http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/

http://www.cnblogs.com/javanerd/p/4504482.html