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

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

假设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个数字中的任意一个。可以轻易证明,在这个过程中每个数字被选中的概率都相等。