假设您有存储k元素的内存。将第一个k元素存储在数组中的内存中。现在，当您收到第n个元素（其中n > k）时，请r在1和之间生成一个随机数n。如果r > k丢弃nth元素。否则取代r第与阵列中的元素n次元素。

这种方法将确保您的数组在任何阶段都将包含k从到目前为止收到的输入元素中统一随机选择的元素。

证明 我们可以通过归纳
证明k任何阶段的代表性元素均以均匀随机的方式分布。假设在接收n-1元素之后，数组中所有元素的概率为k/(n-1)。

收到第n个元素后，该元素将被插入数组=的概率k/n。

对于任何其他元素，它在当前迭代中表示的概率=在先前迭代中表示的概率*在当前迭代中未被替换的概率

= (k/(n-1)) * (n-1)/n = k/n.