给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？
首先对于先出现的1000个关键字,肯定都是妥妥的放到数组里, 当n>1000时, 我们要保证第n个关键字被取到的概率是1000/n的机会随机跟前面1000个替换一个 即可以达到随机抽取.
证明:
对于第n个关键字, 以1000/n概率替换到数组中, 所以选取的概率为1000/n
对于数组中的1000 个数据i(i=1-1000), 按照数学归纳法, 在 取到第 n 个关键字时, i在数组中的概率为1000/(n-1) .
其不被替换出去的概率为 999/1000 (不是它被替换)*1000/n+ 1-1000/n (n没得到机会替换). 所以第i个关键字留在数组中的概率是:
1000/(n-1) *[999/1000*1000/n + 1-1000/n] = 1000/n
对于每一个n>1000 , 所有关键字都以概率1000/n 留在数组中
谷歌笔试题：如何随机选取1000个关键字,布布扣,bubuko.com
谷歌笔试题：如何随机选取1000个关键字
原文：http://blog.csdn.net/ltianchao/article/details/22743075
