一道算法题——从数据流中随机去m个数
题目：有一个很大很大的输入流，大到没有存储器可以将其存储下来，且只输入一次，如何从这个输入流中随机取得m个记录。

我的思路：

首先，存储开始的m条记录，存放于数组result[m]中；

然后，假设有n条记录，每一次读取记录后，取随机数x，0<= x < n；
判断随机数，
当0<= x < m时，我们将记录存放到result[x]中；
当m<= x < n时，我们不存这个记录；

最后，输入所有的数据流后，result[m]存放的就是随机出来的m条记录。

分析下，我们期待的某一个记录被选中的概率为m/n，按照我的这个算法，第i个记录被选中的事件可以描述成“该记录被选在数组里并且后面的记录都没有替代这个位置”，概率为

p = m/n * (1- 1/n)^(n-m-i)

很显然，这个对于所有的i，这个值都是趋近于m/n的。算法结果应该是正确的。
欢迎踊跃拍砖！