蓄水池算法

题目描述

你的公司想要开一个活动,每个用户都能抽奖,但是最终只有$M(M=10)$个用户能中奖。

当一个用户点击抽奖按钮,你的后台会收到他的账号

但是你不知道什么时候活动结束,你也没办法储存所有的账号,如何保证活动结束时,你能随机选出10个用户来?

抽象

给你一个数据流,数据流中的数据个数N未知,你需要从中选出M(M<=N)个不重复的数据,用什么样子的策略能保证随机取到每个元素。

时间复杂度要求: O(N)

空间复杂度要求: O(M)

数学归纳法

假设N=X

假设X=M, 则我们全选即可

假设X>M, 对于数据流的前X个数据,我们从中取出了M个数据,并且这X个元素中每一个元素被选到的概率都相同,恰好为$\frac{M}{X}$, 当数据流中又出现了一个数据的时候,我们希望这个数据被选中的概率为$\frac{M}{X+1}$, 希望前X个数据出现的概率也是$\frac{M}{X+1}$,这个数字比$\frac{M}{X}$小,那我们应该用最后一个数字将其替换,即我们用$\frac{M}{X+1}$的概率选择最后一个数字,并让他随机替换前M个数字中的任意一个。可以轻易证明,在这个过程中每个数字被选中的概率都相等。

转载自 蓄水池抽样算法(Reservoir Sampling)