[面经]一道关于随机算法的面试题
今天碰到了一道面试题：原题大致是，每首歌曲都是一个评分，现在有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实现如下:
class RandomSong(val rate: Array[Double]) { val rateWithIndex = rate.map(x => (x * 10).toInt).zipWithIndex val songPool = rateWithIndex.flatMap { case (rate, index) => Array(index).padTo(rate, index)} def pickSong:Int = songPool(Random.nextInt(songPool.size)) }
测试
object main { def main(args: Array[String]) { val r = new RandomSong(Array(0.9,0.9,0.1,0.2)) var count: Map[Int, Int] = Map() 1 to 10000 foreach { x => val song = r.pickSong count.get(song) match { case None => count += (song -> 1) case Some(n) => count += (song -> (1 + n)) } } println("count = " + count) } }
结果
count = Map(2 -> 477, 1 -> 4312, 3 -> 970, 0 -> 4241)
ps：我是回家路上才想起这种解法的，我和我老婆说，化学系毕业的她直接就给出了正确的解法，哎，被数学学霸碾压的滋味就是这么销魂。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
