- 论坛徽章:
- 8
|
分析:
由于N无法确定,数据只能读取一次,并且要求随机,就是每个元素抽出的概率一样,都是k/N。
面试的时候,经常会在纸上通过一个小的例子来找到好的解决方案。比如先让你从100个元素中等概率抽取出10个元素。后来又向集合中添加了20个元素,变成了120个元素等概率抽取10个,怎么样才能随着N的动态改变而让N无论等于多少时这N个元素都等概率被抽取呢?
解法一:最小k个指纹
找到一个哈希函数能产生随机数,同时用一个k个元素的堆用来保存最小的k个元素。那么过一遍所有的元素,计算每个的哈希值,通过堆来选择k个元素。
这个算法看起来很精妙,会有什么问题吗?(思考)
解法二:数学计算
先选中前k个, 从第k+1个元素到最后一个元素为止, 以1/i (i=k+1, k+2,...,N) 的概率选中第i个元素, 并且随机替换掉一个原先选中的元素, 这样遍历一次得到k个元素, 可以保证完全随机选取。
看来简单的算法,怎么能确保每个元素被选中的概率是k/N?
任意元素G在i轮留下来的概率:
P(G留下) = P(G已经存在) * P(G没有被替换)
= P(G已经存在) * (1 - P(G被替换))
= P(G已经存在) * (1 - P(第i个元素要替换某个元素) * P(某个元素是G))
= (k/i) * (1 - (k/(i+1)) * (1/k))
= (k/i) * (1 - (1/(i+1)))
= (k/i) * (i/(i+1))
= (k/(i+1))
证毕! |
|