水塘抽样

    1. class Solution {
    2.     map<int, vector<int>> mp;
    3. public:
    4.     Solution(vector<int>& nums) {
    5.         for(int i = 0; i < nums.size(); i++)
    6.         {
    7.             if(mp.find(nums[i]) == mp.end())
    8.             {
    9.                 mp[nums[i]] = vector<int>({i});
    10.             }
    11.             else
    12.             {
    13.                 mp[nums[i]].push_back(i);
    14.             }
    15.         }
    16.     }
    18.     int pick(int target) {
    19.         vector<int> v = mp[target];
    20.         return v[rand()%v.size()];
    21.     }
    22. };
    24. /**
    25.  * Your Solution object will be instantiated and called as such:
    26.  * Solution* obj = new Solution(nums);
    27.  * int param_1 = obj->pick(target);
    28.  */