b***k
发帖数: 2673 | 1 ☆─────────────────────────────────────☆
simple1987 (simple) 于 (Mon May 4 15:14:09 2009) 提到:
a new interview question I just had.
一个set,不知道element个数。
目标：设计strategy,取出k个elements,且使得每个element被选择的概率相同。
限制：只允许遍历一次。
☆─────────────────────────────────────☆
gatsby (gatsby) 于 (Mon May 4 15:30:53 2009) 提到:
不知道是不是正确理解了题目,先把前k个取出来,然后读入一个新的element,有1/(k+1)
的概率这个新的element会被选中,如果被选中,就randomly替换已经被选的k个element
中的一个.如果没有被选中,就读入下一个element.然后重复上面的步骤,不过,被选中概
率换成1/(k+2),不断下去.直到读完全部数据,最后选出的k elements就符合要求. |
|
