這道題是一道時(shí)間換空間的題枢步，用map來保存index過不了大數(shù)據(jù)。想考水塘抽樣的原理(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;
}
};
