Random Pick Index (Leetcode 398)

这道题是一道时间换空间的题，用map来保存index过不了大数据。想考水塘抽样的原理(Reservoir sampling)

class Solution {
    vector<int> nums;
public:
    Solution(vector<int> nums) {
        if(nums.empty()) return;
        this->nums = nums;
    }
    
    int pick(int target) {
        int cnt = 0, ret = 0;;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] == target){
                cnt++;
                int rand_idx = rand() % cnt;
                if(rand_idx == 0) ret = i;
            }
        }
        return ret;
    }
};