[数据结构与算法]水塘抽样法

什么是水塘抽样法

在抽样的样本大小未知的情况下需要等概率选出一个数的时候推荐使用

原理：
遇到符合条件的数时选择的概率为1/n,n目前的元素个数，这样做每个数最终被选到的概率是相等的

证明：
客观来看
遇到第1个数时，第一个数被选择的概率为1/1
遇到第2个数时，第一个数被选择的概率为1/11/2=1/2，第二个数被选择的概率为1/2
遇到第3个数时，第一个数被选择的概率为1/11/22/3=1/2，第二个数被选择的概率为1/22/3=1/3，第三个数被选择的概率为1/3
推下去每个数被选择的概率都是一样的

为什么要使用水塘抽样法

在数组中等概率选择一个符合条件的数，例如有一个数组有10个元素：5，3，4，8，6，9，1，2，7，10；
随机选择一个数

直接用rand(),时间复杂度为O(1)

#include<iostream>
using namespace std;
int main(){
	int a[10]={5,3,4,8,6,9,1,2,7,10};
	cout<<a[rand()%10]; 
} 
//console:
//3

水塘抽样法O(n)

#include<iostream>
using namespace std;
int main(){
	int a[10]={5,3,4,8,6,9,1,2,7,10};
	int select;
	int n=1;
	for(int i=0;i<10;i++){
		if(rand()%n==0){
			select=a[i];
			n++;
		}
	}
	cout<<select;
} 
//console:
//10

但加入在题目中加个条件在数值>=5的数中选择1个数，就不能直接用rand()了，往往需要经过处理，时间或空间复杂度达不到最优，而水塘抽样法可以在时间复杂度O(n)、空间复杂度O(1)的情况下完成选择

#include<iostream>
using namespace std;
int main(){
	int a[10]={5,3,4,8,6,9,1,2,7,10};
	int select;
	int n=1;
	for(int i=0;i<10;i++){
		if(a[i]>=5&&rand()%n==0){
			select=a[i];
			n++;
		}
	}
	cout<<select;
} 
//console:
//6

注意：
为什么代码每次运行答案都是确定的呢？因为rand()的种子是一样的，每次运行rand()的值都是唯一确定的，并不能做到每次都随机，rand()的概念是在理论上每个数出现的次数都一样而使得总概率而已，并不是随机概率相等