一、引言
最近小黄的朋友去一家业内有名的游戏公司（有兴趣的读者可以猜猜）面试，出了一道经典的题目：目前游戏需进行一项签到抽奖的活动，怎么保证每个人抽到奖品的概率都是相等的，保证最终中奖的人数为10人
小黄的朋友计算出 签到的总人数，使用随机函数Random 获取 中奖的人，依次类推，最终求出 10个中奖的人
但面试官并不满意该做法，提出了几个条件：
- 签到的人数
N很大且不可知 - 随机选取
10个人，每个人被选中的概率为10/N
- 时间复杂度为
O(N)
小黄朋友瞬间有点懵了，不知所措，聊了聊其他的，潦草的结束了这场面试
朋友找小黄聊了聊，最终发现面试官想考察的是：蓄水池抽样算法（Reservoir Sampling）
有精力的读者可以事先看一下这几道 模板 题：
二、蓄水池抽样算法
由人数 N 不可知、每个人选中的概率为 10/N、时间复杂度为 O(N) 这几个条件我们可以得知：我们的算法肯定是遍历一次，每个人选中的概率随着签到人数的增加，逐渐变小，但每个人选中的概率一样
比如 num 代表我们逐渐增长的人数：for(int num = 1; num <= 100; num++)
- 当
num = 10时，我们每个人数选取的概率为10/10 - 当
num = 50时，我们每个人数选取的概率为10/50
- 当
num = 100时，我们每个人数选取的概率为10/100
我们可以看到，随着人数动态的增加，我们的概率也变的不同，如果我们单纯的使用上面 Random 的算法，对于动态的调整我们没有办法
下面，我们一起来领略一下 蓄水池抽样算法 的奥妙所在
1. 思路
我们总体的水池如下：
当前的 num <= 10 时，我们直接让其入水池
当前的 num > 10 时我们在 1~num 进行随机
- 如果随机的结果小于等于10，则替换该水池
- 如果随机的结果大于10，则不做操作
假设当前的值为 12，我们使用 random.nextInt(12) + 1 得到 1~12 的随机值
- 假如随机值为
5，则12将替换池中下标为5的数
- 假如随机值为
11，则不做操作
最终蓄水池中的数字即为签到中奖的人数
到这一步，我相信 80% 的人会懵，没关系，我也是这样过来的
让我们一起来下面的证明
2. 证明
我们假设当前的 num 为 30，那么每一个值被选中的概率为 10/30
首先，我们证明 3 的概率：
对于 3 来说，入水池概率： 100%100，出水池的概率 = 被替换的概率（也就是 num > 10）
11能够替换3的概率：(10 / 11) * (1 / 10) = (1 / 11)（替换水池的概率 * 随机水池为3的概率）
12能够替换3的概率：(10 / 12) * (1 / 10) = (1 / 12)- …
- 我们反过来想一下，那么我们
3不出水池的概率为多少呢？
(3)进水池的概率 * (3)不出水池的概率
1 * (10 / 11) * (11 / 12) * (12 / 13) * ... (29 / 30) = (10 / 30)- 符合我们最后的结果
最后，我们证明 17 的概率：
对于 17 来说，入水池概率：10 / 17，出水池的概率 = 被替换的概率（也就是 num > 17）
18能够替换17的概率：(10 / 18) * (1 / 10) = (1 / 18)（替换水池的概率 * 随机水池为17的概率）
19能够替换17的概率：(10 / 19) * (1 / 10) = (1 / 19)- …
- 我们反过来想一想，那么我们
17不出水池的概率为多少呢？
(17)进水池的概率 * (17)不出水池的概率
(10 / 17) * (17 / 18) * (18 / 19) * (19 / 20) * ... (29 / 30) = (10 / 30)- 符合我们最后的结果
3. 代码
public class _蓄水池算法 { static Random random = new Random(); public static void main(String[] args) { // 10000组测试 int test = 10000; // 人数为100人 int dataBase = 100; // 记录每次出现的频率 int[] count = new int[101]; for (int i = 0; i < test; i++) { // 蓄水池 int[] bag = new int[10]; // 蓄水池下标 int bagIndex = 0; for (int num = 1; num <= dataBase; num++) { // 如果小于10,直接入池 if (num <= 10) { bag[bagIndex++] = num; } else { // 如果大于10,则以 10 / i 的概率观察是否可以入池 // 如果小于等于10,则证明可以入池 if (getNum(num) <= 10) { // 随机淘汰池里面的一个数 int index = random.nextInt(10); bag[index] = num; } } } // 记录当前出现的频率 for (int num : bag) { count[num]++; } } // 输出、验证我们的随机率 for (int i = 0; i < count.length; i++) { System.out.println(count[i]); } } // 返回[1,i]的数 public static int getNum(int i) { return random.nextInt(i) + 1; } }
测试结果：我们发现出现的频率基本相等
999 1009 967 1050 981 996 996 950 971 998 1005 1032 974 982 1007 1029 1026 1045
三、例题练习
俗话说的好，一看就会，一做就废，验证你成果的时候到了
力扣模板题目：
基本就是模板题，直接套上面的公式即可
四、总结
基本蓄水池抽样算法到这里就结束了
在工程上主要应用于 抽奖系统，这里可能有人会疑问，我直接等抽奖完毕，然后计算总人数，不也能达到一样的效果嘛。从效果来看，没什么区别性。
但是，工程和理想最大的区别就是：工程可能由于一系列的外在因素影响正常流程的运行。
比如，原本我计划在 2022.1.8~2022.1.10 进行为期2天的抽奖，开奖时间设置在 2022.1.11，如果服务器宕机，导致数据丢失，怎么保证最终的总人数。而我们的 蓄水池抽样算法 则是会一直更新中奖的人数。
当你遇到这类面试题时，直接三步走：原理 -> 证明 -> 代码，一波带走面试官
