398. 随机数索引

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

注意：

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

示例:

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);

嗯这道题我只会用dict做，用一个然后每个键值对应一个idx的列表

看了下题解，defaultdict是可以在没有value值时返回某人值的~

class Solution:

    def __init__(self, nums: List[int]):

        self.nums_idx_map=defaultdict(list)

        for i,nums in enumerate(nums):

            self.nums_idx_map[nums].append(i)

    def pick(self, target: int) -> int:

        return random.choice(self.nums_idx_map[target])

然后我看题解给了个更高效的算法：大数据抽样法

所以可以以1/k的概率进行更新，就可以保证概率相同