水塘抽样

    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. }
    17. int pick(int target) {
    18. vector<int> v = mp[target];
    19. return v[rand()%v.size()];
    20. }
    21. };
    22. /**
    23. * Your Solution object will be instantiated and called as such:
    24. * Solution* obj = new Solution(nums);
    25. * int param_1 = obj->pick(target);
    26. */