分析
用一个哈希表存储相同数字的所有下标
询问的时候直接输出该数字所对应数组里的一个随机值即可。
C++ 代码
class Solution {
public:
unordered_map<int,vector<int> > mp; //一个数字对应一个下标数组
Solution(vector<int>& nums) {
for(int i=0;i<nums.size();i++)
{
mp[nums[i]].push_back(i);
}
}
int pick(int target) {
return mp[target][rand()%mp[target].size()]; //返回目标值的下标数组中的随机值
}
};