题目

难度：★★☆☆☆
类型：数组
方法：数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);

// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

解答

这是一个随机采样问题。我们在初始化时构造一个字典，用来统计所有数字出现的下标。字典的键是数字，值是该数字所在的位置，由于数字可能有重复，所以数字出现的位置可能有很多，因此用列表的形式给出。

在调用时，选取该数字出现的位置列表，然后进行随机采样即可。

import random


class Solution:

    def __init__(self, nums):
        self.num_dict = dict()
        for index, num in enumerate(nums):
            if num not in self.num_dict.keys():
                self.num_dict.update({num: [index]})
            else:
                self.num_dict[num].append(index)

    def pick(self, target: int) -> int:
        index_list = self.num_dict[target]
        selected_index = int(random.random() * len(index_list))
        return index_list[selected_index]

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析