Resevior Sampling

Randomly return the index of maximal elements in the array.
follow up: 要求linear time 和constant space

先把前k个数放入蓄水池，对第k+1，我们以k/(k+1)概率决定是否要把它换入蓄水池，换入时随机的选取一个作为替换项，这样一直做下去，对于任意的样本空间n，对每个数的选取概率都为k/n。也就是说对每个数选取概率相等。

• Create an array reservoir[0..k-1] and copy first k items of stream[] to it.
• Now one by one consider all items from (k+1)th item to nth item.
• Generate a random number from 0 to i where i is index of current item in stream[]. Let the generated random number is j.
• If j is in range 0 to k-1, replace reservoir[j] with arr[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public int findMax(vector<int> &arr){
	int len = arr.length();
	int ret =-1, max = INT_MIN;
	int count=0;
	for(int i=0; i<len; i++){
		if(arr[i]==max){
			count++;
			srand(time(NULL));
			int judge = rand()%count;
			if(judge==0){
				ret = i;
			}
		}
		else if(max==INT_MIN || arr[i]>max){
			max = arr[i];
			ret = i;
			count=1;
		}
	}
	return ret;
}