前置知识：

• 数学

面向面试编程-蓄水池算法

题目要求

给定一个极其大的数据流，大到无法存入内存，要求在所有数据中随机选取k个元素。

解法：蓄水池算法

假设读取第i个数据，从1开始计数。如果i小于等于k，则存入蓄水池。如果i大于k，则随机取从1到i之间的随机数m，如果m处于1到k中，那么将i元素替换蓄水池中m元素。
证明
对于蓄水池中的元素，被选中的概率是不被蓄水池外的元素替换掉的概率。即k×(k+1)×…×(N-1)/((k+1)×(k+2)×…×(N)) = k/N。
对于蓄水池外的元素，假设位置i，那么概率为选中的概率乘以不被后面元素替代的概率。即(k/i)×(i/(i+1))×…×((N-1)/N) = k/N。