蓄水池算法
fightinggg
3月 29, 2021
题目描述
你的公司想要开一个活动，每个用户都能抽奖，但是最终只有$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个数字中的任意一个。可以轻易证明，在这个过程中每个数字被选中的概率都相等。