[Algorithm]Reservoir Sampling

假设存在一个数据流，长度为N。但我们事先不知道其长度，我们想从数据流中选出k(k <= N)个数据，如何保证选到的k个数据是随机的？换句话说，如何保证每个元素被选到被选择的改路是k / N？Reservoir sampling就是用来解决这类问题的算法，具体步骤如下：

1. 将数据流前k个数据([0, k - 1])加入结果集
2. 对于[k, N - 1]中的数据i，我们随机生成一个[0, i]的数字r，如果0 <= r <= k - 1，我们把数据i加入结果集，把数据r移出结果集

这样对于数据流中的数据，我们有如下结论：

• 对于前k个数，其最终留在结果集中的概率为(k / (k + 1)) * ((k + 1) / (k + 2)) * ... * ((N - 1) / N) = k / N
• 对于[k, N - 1]的数据i，其被换入结果集的概率为k / i，留在结果集不被换出的概率为(i / (i + 1)) * ((i + 1) / (i + 2)) * ... * ((N - 1) / N)，两者相乘结果为k / N

我们用Linkedlist来代表数据流，代码如下：

	struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	};
	vector<int> getRandom(ListNode* head, int k) {
	vector<int> res(k);
	int count = 0;
	ListNode* curr = head;
	while(curr)
	{
	if(count < k)res[count] = curr->val;
	else
	{
	int random = rand() % (count + 1);
	if(random < k)res[random] = curr->val;
	}
	curr = curr->next;
	++count;
	}
	return res;
	}

view raw reservoir_sampling.cpp hosted with ❤ by GitHub