蓄水池算法

问题描述：

1.从10000个编号为1-10000的人中随机抽100个调查

2.从80亿个编号为1-80亿的人中随机抽取100个调查

对于第一个问题，可以把10000个人的信息读取到数组中，调用库函数rand()，随机访问。第二个问题也可以读取到数组中，显然，这种方法不可取。

问题描述：要求从N个元素中随机的抽取k个元素，其中N无法确定。

问题定义可以简化如下：在不知道文件总行数的情况下，如何从文件中随机的抽取一行？

给出解决方案：在扫描第i个行时，以1/i的概率选择该行，选择意味着选取当前行并替换前面已经选到的那行。即，扫描到第一行时，选择；扫描到第二个行时，以1/2的概率替换第一个行；扫描到第三个行时，以1/3的概率替换前面选取的行，以此类推，直至扫描完一遍后，选取到的行号恰好是等概率的。

证明：设行号为[1…N]，即证明选取每行的概率为1/N。设1<= i <=N，选取到第i行的事件为第i次选取了第i行且后面每次选择过程中均没有选中。概率为：抽到第i行的概率( $\frac{1}{i}$ ) ** 抽到第i行但是没有替换第i行的概率(1 - $\frac{1}{n}$ ) **。比如说抽到第三行时，第三行出现的概率为( $\frac{1}{3}$ )，但是没有选中第三行的概率是(1 - $\frac{1}{3}$ )

p = $\frac{1}{i}$ ??????X (1 - $\frac{1}{i + 1}$ ??????)X (1 - $\frac{1}{i + 2}$ ??????)X (1 - $\frac{1}{i + 3}$ ??????)X (1 - $\frac{1}{i + 4}$ ??????)X …X (1 - $\frac{1}{n}$ ???????)

= $\frac{1}{i}$ ????????X ( $\frac{i}{i + 1}$ ????????)X ( $\frac{1 + i}{i + 2}$ ????????)X ( $\frac{i + 2}{i + 3}$ ????????)X ( $\frac{i + 3}{i + 4}$ ????????)X …X ( $\frac{n - 1}{n}$ ??????????)

= $\frac{1}{n}$

在不知道行数的情况下，如果遍历到最后一行，保留的仍然是第一行的情况

第一行，抽到第一行的概率为：1

第二行，抽到第二行的概率为: $\frac{1}{2}$ ?，抽到第二行但是没有替换第一行的概率，1 x ( 1 - $\frac{1}{2}$ ?) = $\frac{1}{2}$ ?，如果行数为2，那么1，2出现的概率都为 $\frac{1}{2}$ ?

第三行，抽到第三行的概率为： $\frac{1}{3}$ ，抽到第二行但是没有替换第一行的概率，1 x (1 - $\frac{1}{2}$ ) x (1 - $\frac{1}{3}$ ) = $\frac{1}{3}$ ，如果行数为3，那么1，2，3出现的概率都为 $\frac{1}{3}$ ?

第四行，抽到第四行的概率为： $\frac{1}{4}$ ，抽到第二行但是没有替换第一行的概率，1 x (1 - $\frac{1}{2}$ ) x (1 - $\frac{1}{3}$ ) x (1 - $\frac{1}{4}$ ) = $\frac{1}{4}$ ，如果行数为4，那么1，2，3，4出现的概率都为 $\frac{1}{4}$ ?

…

第n行，抽到第n行的概率为： $\frac{1}{n}$ ??，抽到第n行但是没有替换第一行的概率，1 x (1 - $\frac{1}{2}$ ??) x (1 - $\frac{1}{3}$ ??) x (1 - $\frac{1}{4}$ ??)x…x (1 - $\frac{1}{n}$ ??) = $\frac{1}{n}$ ?，如果行数为n，那么1，2，3，4,…,n出现的概率都为 $\frac{1}{n}$ ??

推导完毕。第n行的原理也如此。

LeetCode 382.链表随机节点

题目描述：

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

代码实现

class Solution {
private:
    ListNode* head;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
    }

    /** Returns a random node's value. */
    int getRandom() {
        ListNode* head = this->head;
        int k = 1;
        int val = head->val;
        while (head) {
            //在[0, k - 1]间，随机选一个数
            int num = rand() % k;
            //选中0的概率为：(1/k)，如果为0代表选中第k - 1行，然后替换。p = 1 / k
            //未选中0的概率为(1 - 1/k)，不替换，保留上次的结果。p = 1*(1-1/2)*(1-1/3)*...*(1-1/n)
            if (num == 0) {
                val = head->val;
            }
            k++;//k++，模拟行数的增加
            head = head->next;
        }
        return val;
    }
};

LeetCode 398.随机数索引

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。您可以假设给定的数字一定存在于数组中。

注意：
数组大小可能非常大。使用太多额外空间的解决方案将不会通过测试。

示例:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);

// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

class Solution {
    vector<int>nums;
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
    }

    int pick(int target) {
        int n = nums.size();
        int k = 1;
        int index = 0;
        for (int i = 0; i < n; i++) {
            if (this->nums[i] == target) {
                if (rand() % k == 0) {
                    index = i;
                }
                k++;
            }
        }
        return index;
    }
};

提取k个时。

在这里插入图片描述

array S[n];    //source, 0-based
array R[k];    // result, 0-based
integer i, j;
 
// fill the reservoir array
for each i in 0 to k - 1 do
        R[i] = S[i]
done;
 
// replace elements with gradually decreasing probability
for each i in k to n do
        j = random(0, i);   // important: inclusive range
        if j < k then
                R[j] = S[i]
        fi
done