蓄水池算法

假设有一个源源吐出不同球的机器，只有装下10个球的袋子，每一个吐出的球，要么放入袋子，要么永远扔掉如何做到机器吐出每一个球之后，所有吐出的球都等概率被放进袋子里

什么是蓄水池算法

蓄水池算法（Reservoir Sampling Algorithm）是一种随机算法，用于从未知数量的数据流中随机选择 k 个元素，其中 k 为预设的正整数。该算法的主要思想是在不知道数据流长度的情况下，通过随机选择 k 个元素并将其标记为“蓄水池”，然后从第 k+1 个元素开始，每个元素被选中的概率与之前未被选中的元素数量成比例。

以下是蓄水池算法的详细步骤：

初始化：将前 k 个元素标记为“蓄水池”，并将其余元素标记为未选中
从第 k+1 个元素开始遍历数据流：对于每个新元素，以 k/n 的概率将其标记为“蓄水池”（其中 n 是数据流中元素的总数）。如果元素被标记为“蓄水池”，则将其加入蓄水池中，并从数据流中移除。如果元素未被标记为“蓄水池”，则将其保留在数据流中。
重复步骤 2 直到数据流中的所有元素都被处理

在完成蓄水池算法后，我们可以得到一个大小为 k 的随机样本，其中每个元素被选中的概率相等。由于算法是随机的，因此无法保证样本的准确性，但可以证明，当数据流中的元素数量足够大时，样本的准确性接近于 1。

蓄水池算法的时间复杂度为 O(mn)，其中 m 是数据流中的元素数量，n 是每个元素的复杂度，因为需要对每个元素进行标记和移除操作。

代码演示

public static class RandomBox{private int[] bag;private int N;private int count;/*** 初始化* @param capacity*/public RandomBox(int capacity){bag = new int[capacity];N = capacity;count = 0;}/*** 返回[1 , max] 上任何一个随机数*/public int rand(int max){return (int)(Math.random() * max) + 1;}/*** 加入的规则* @param num*/public void add(int num){count++;//袋子没有满时,直接放进去.if (count <= N){bag[count - 1] = num;}else {//    (N / count) 的概率放进袋子中 if (rand(count) <= N){//袋子中(1 / N) 的概率选中一个 仍出去bag[rand(N) - 1] = num;}}}}