398. Random Pick Index

reservoir sampling O(n) time O(n) space
大小为1的水塘采样
從S中抽取首k項放入「水塘」中
對於每一個S[j]項（j ≥ k）：
隨機產生一個範圍從0到j的整數r
若 r < k 則把水塘中的第r項換成S[j]項
这道题里的k为1，所以目标随机下标r为0
证明：假设最后一个被选中的是i，则i之前是否选中不重要，概率乘积为1，之后都不能被选中，假设target共有n个，则i被选中的概率为1/i * i/(i + 1) * … * (n - 1)/n = 1/n

class Solution {
public:
    Solution(vector<int> nums) : nums(move(nums)) {
        srand((unsigned)time(NULL));
    }

    int pick(int target) {
        int res = -1;
        for (int i = 0, count = 0; i < nums.size(); ++i) {
            if (nums[i] != target) continue; // 跳过所有的非目标，采样跟他们无关
            if (rand() % ++count == 0) { // 遇到目标时随机一次，这样采样数据源只包括所有的目标
                res = i;
            }
        }
        return res;
    }

    vector<int> nums;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

class Solution {
public:
    Solution(vector<int> &nums) : b(begin(nums)), e(end(nums)) {
        srand((unsigned)time(NULL));
    }

    int pick(int target) {
        int res = -1, count = 0;
        for (auto it = b; it != e; ++it) {
            if (*it != target) continue;
            if (rand() % ++count == 0) {
                res = distance(b, it);
            }
        }
        return res;
    }

    vector<int>::iterator b, e;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */