Random Pick Index

题目来源
给一个数组存在重复元素，给一个元素，随机选取数组中该元素所在位置。
我想着直接用哈希，存储每个元素对应的位置，然后内存溢出了。

class Solution {
public:
    Solution(vector<int> nums) {
        int n = nums.size();
        for (int i=0; i<n; i++) {
            maps[nums[i]].push_back(i);
        }
    }
    
    int pick(int target) {
        int n = maps[target].size();
        int r = rand() % n;
        return maps[target][r];
    }
private:
    unordered_map<int, vector<int>> maps;
};

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

难道还能不存储位置？看了下tags，蓄水池抽样。就是未知数目的元素，取样k个，然后前k个都取。假设取到第p个的时候，取该数的概率是k/p，然后随机替换k个中的一个。

class Solution {
public:
    Solution(vector<int> nums) {
        this->nums = nums;
    }
    
    int pick(int target) {
        int n = nums.size();
        int res = 0, cnt = 0;
        for (int i=0; i<n; i++) {
            if (nums[i] == target) {
                cnt++;
                if (cnt == 1)
                    res = i;
                else {
                    int r = rand() % cnt;
                    if (r == 0)
                        res = i;
                }
            }
        }
        return res;
    }
private:
    vector<int> nums;
};

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