从今天开始每日一题打卡,不间断,冲!

题目描述

  话不多说,先放题目链接和题目截图,398.随机数索引,题目如下图所示:

image-20220425215428606

题目分析

  一般人看到这道题的思路就是使用哈希表去做,首先建立一个哈希表,表的key是数组里的元素,表的value是每个元素在数组中的下标数组。那么在pick函数里,首先根据元素的值在哈希表中获取其的下标数组,然后根据下标数组的长度生成随机数,根据随机数取出我们需要的下标。

  当然如果学过水塘抽样的算法的话,那么这道题可以用抽样的思路去做。题目里有这样的一个限制,那就是对于重复的数字,我们随机返回其索引。那么对于水塘抽样的话,我们的思路可以是这样,假设在数组中,我们的target数有k个,那么我们可以这样做,首先遍历数组,当遍历的第i个target的时候,我们生成[0,i)的随机数,如果随机数等于0,那么我们就记录i为我们需要返回的索引。这个我们也可以使用数学证明一下,思路如下:(如果这块还没理解,我们待会儿看看代码就理解了)

image-20220425223210057

代码实现

  对于使用哈希表的思路,我们的代码如下,使用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就近一点点

Q.E.D.


 研究僧一名,CV领域,研究方向为对抗攻击,欢迎各位前来交流