398. 隨機(jī)數(shù)索引

給定一個可能含有重復(fù)元素的整數(shù)數(shù)組，要求隨機(jī)輸出給定的數(shù)字的索引。 您可以假設(shè)給定的數(shù)字一定存在于數(shù)組中。

注意：

數(shù)組大小可能非常大。 使用太多額外空間的解決方案將不會通過測試。

示例:

int[] nums = new int[] {1,2,3,3,3};

Solution solution = new Solution(nums);

// pick(3) 應(yīng)該返回索引 2,3 或者 4。每個索引的返回概率應(yīng)該相等。

solution.pick(3);

// pick(1) 應(yīng)該返回 0。因為只有nums[0]等于1。

solution.pick(1);

嗯這道題我只會用dict做，用一個然后每個鍵值對應(yīng)一個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])

然后我看題解給了個更高效的算法：大數(shù)據(jù)抽樣法

所以可以以1/k的概率進(jìn)行更新，就可以保證概率相同