水塘抽样
class Solution {
map<int, vector<int>> mp;
public:
Solution(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++)
{
if(mp.find(nums[i]) == mp.end())
{
mp[nums[i]] = vector<int>({i});
}
else
{
mp[nums[i]].push_back(i);
}
}
}
int pick(int target) {
vector<int> v = mp[target];
return v[rand()%v.size()];
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* int param_1 = obj->pick(target);
*/