每日一题——398. 随机数索引

398. 随机数索引

自己从英文机翻了一遍题目 官中说的一般般 感觉还是英语详细

给定一个可能具有重复项的整数数组nums，随机输出给定目标数的索引。可以假设给定的目标数必须存在于数组中。

实现Solution class:

Solution class:(int[] nums)使用数组nums初始化对象。

int pick(int target)：从nums中选取一个随机索引i，其中nums[i] == target。

如果有多个有效的i，那么每个索引返回的概率应该相等。

示例1:

输入

[“Solution”， “pick”， “pick”， “pick”]

[[[1,2,3,3,3]]， [3]， [1]， [3]]

输出

[null, 4, 0, 2]

解释
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick (3);//它应该随机返回索引2、3或4。每个指数应该有相等的回报概率。
solution.pick (1);//它应该返回0。因为在数组中只有nums[0]等于1。
solution.pick (3);//它应该随机返回索引2、3或4。每个指数应该有相等的回报概率。

约束:

1 <= nums.length <= 2 * 10^4
-231 <= nums[i] <= 231 – 1

Target是nums中的一个整数

最多要104次请求来挑选

---

哈希表存放索引 然后随便输出一个出来

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()];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */

水塘抽样

之前没有接触过这个东西

遍历nums 第i次遇到值为target的元素 就随机选择区间[0,i)内的一个整数

如果等于0，就返回值置为该元素的下标，否则返回值不变

概率均为1/k

这个写法我真看不大懂

class Solution {

vector<int> &nums;  

public:
    Solution(vector<int>& nums):nums(nums)
    {

    }
    
    int pick(int target) {
        int ans;
        for(int i = 0,cnt =0; i< nums.size();i++)
        {
            if(nums[i] == target)
            {
                cnt++;
                if(rand()% cnt == 0)
                {
                    ans = i;
                }
            }
        }

        return ans;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */