蓄水池抽样

要解决的问题：不知道有多少个元素的情况下，随机选取m个数字，并使得每个数字被选择的概率相同。

解决方法：从前开始处理每个样本，==并使得每个样本的概率为$1/i$==，其中$i$为样本编号（编号从1开始），最终可以确保每个样本成为答案的概率为$1/n$（其中$n$​为样本总数）。

推理如下：

image-20220116123032058

化简得：

image-20220116123110609

最终结果为：

image-20220116123311874

代码如下：

1
2
3
4
5
6
7
8
9
10
11
int getRandom() {
        int idx=0;
        int ans=0;
        auto tmp=head;
        while(tmp){
            idx++;
            if(rand()%idx==0) ans=tmp->val;
            tmp=tmp->next;
        }
        return ans;
    }

上述的if(rand()%idx==0) ans=tmp->val;代表选中该数字。