Reservoir sampling

应用

水塘取样的方法常被用于在不知道数据总大小／数组总长度的情况下，进行随机数选取，保证取到的数的概率等于1/n。n为当前已知数据的数量。

算法

这篇文章讲的很好：https://www.iteblog.com/archives/1525 用自己的话概括一下，就是我们维护一个容量为1的水塘，然后对当前数，我们有1/n的概率使得当前数可以去替换水塘里的candidate，以及1 - 1/n的概率保持水塘里原来的candidate不变。所以我们每次针对[0, n-1]的范围生成随机数，如果它的概率等于1/n （比如当前随机数 % n == 0），那么用它来替换掉水塘里的candidate，否则不变。如此直到我们访问数据结束。

扩展到在大数据里面找k个随机元素的问题，解法就是水塘里维护容量为k的candidates，然后每次生成的随机数的大小<= k的话，说明可以替换掉水塘里的元素，否则保持不变，直到访问数据结束。

题目

• Leetcode 382. Linked List Random Node (这里我们考虑的概率是一个数替换前一个数的概率，也就是成为candidate的概率)
• Leetcode 398. Random Pick Index (这里我们考虑的概率是一个数替换前一个数的概率，也就是成为candidate的概率)
• Leetcode 384. Shuffle an Array (这里我们考虑的概率是一个数留在原来位置上的概率)