本文首发于馆主君晓的博客，04-25每日一题
题目描述
??话不多说，先放题目链接和题目截图，398.随机数索引，题目如下图所示：
题目分析
??一般人看到这道题的思路就是使用哈希表去做，首先建立一个哈希表，表的key是数组里的元素，表的value是每个元素在数组中的下标数组。那么在pick函数里，首先根据元素的值在哈希表中获取其的下标数组，然后根据下标数组的长度生成随机数，根据随机数取出我们需要的下标。
??当然如果学过水塘抽样的算法的话，那么这道题可以用抽样的思路去做。题目里有这样的一个限制，那就是对于重复的数字，我们随机返回其索引。那么对于水塘抽样的话，我们的思路可以是这样，假设在数组中，我们的target数有k个，那么我们可以这样做，首先遍历数组，当遍历的第i个target的时候，我们生成[0,i)的随机数，如果随机数等于0，那么我们就记录i为我们需要返回的索引。这个我们也可以使用数学证明一下，思路如下：（如果这块还没理解，我们待会儿看看代码就理解了）
代码实现
??对于使用哈希表的思路，我们的代码如下，使用c++实现
class Solution {
unordered_map<int, vector<int>> pos;
public:
Solution(vector<int> &nums) {
for (int i = 0; i < nums.size(); ++i) {
pos[nums[i]].push_back(i);
}
}
int pick(int target) {
auto &indices = pos[target];
return indices[rand() % indices.size()];
}
};
??对于使用水塘抽样的思路，我们的代码如下，使用c++实现：
class Solution {
vector<int>& nums;
public:
Solution(vector<int>& nums):nums(nums){
}
int pick(int target) {
int ans = 0;
for(int i = 0,count = 0;i<nums.size();i++){
if(nums[i]==target){
count++;
if(rand()%count==0){
ans = i;
}
}
}
return ans;
}
};
结语
??每天进步一点点，offer就近一点点
