题目

有一个机器按自然数序列的方式吐出球(1 号球,2 号球,3 号球,……)，你有一个袋子，袋子最多只能装下K个球，并且除袋子以外，你没有更多的空间。
设计一种选择方式，使得当机器吐出第N号球的时候(N>K)，你袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是K/N。

举一个更具体的例子。有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10个球，并且1~100号中的每一个球被选中的概率都是10/100。然后继续吐球，当吐出1000个球时，袋子里有10个球，并且1~1000号中的每一个球被选中的概率都是10/1000。继续吐球，当吐出i个球时，袋子里有10个球，并且1~i号中的每一个球被选中的概率都是10/i，即吐球的同时，已经吐出的球被选中的概率也动态地变化。

应用场景:对于网站的抽奖问题，首先网站不可能统计出所有的用户，因为每个用户上线时间不同，其次对于大量用户抽奖，用户信息量十分庞大，因此对资源消耗非常大，所以采用蓄水池算法。一定时间内抽一次奖，这样把不同时段的用户的信息记录下来，进行抽奖，即k=1，最后统一信息宣布结果，也就是用户一上线就确定了中奖的情况

分析

这个问题是蓄水池问题，主要的难点是理解证明过程
解决方案：
首先将前k个球全部放入袋子中，然后对于k以后的球，随机选择是否进入袋子中，如果进入则将其余的球袋子中任意一个球拿出，则所有过程中每个就进入袋子的概率都是k/n.

证明过程
证明过程

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int getRandom(int i){
	//返回(0,i]的整数，即[1,i]
	return (int)(Math.random()*i)+1;
}
public static int[] getNum(int k, int n){
	//蓄水池
	int[] reservoir = new int[Math.min(k, n)];
	//前k个数字直接进入蓄水池
	for (int i = 0; i < reservoir.length; i++) {
		reservoir[i] = i;
	}	
	for(int i = k+1; i < n ; i++){
		//决定i是否进池
		//产生[1,i+1],减1后得到[0,i]
		int cur = getRandom(i+1)-1;
		if(cur <= k - 1){
			//在k之内，就会进入池中，则将池中的任意一个元素拿出
			//产生出[1,k],减1后得到[0,k-1]
			int repalced = getRandom(k)-1;
			reservoir[repalced] = i;
		}
	}
	return reservoir;
}