题目来源
给一个数组存在重复元素，给一个元素，随机选取数组中该元素所在位置。
我想着直接用哈希，存储每个元素对应的位置，然后内存溢出了。
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);
*/
