哈希表 水塘抽样

这题比较有意思，两种解法一种时间换空间 ，一种空间换时间。

方法一 哈希表

思路分析

建立一个key为数组，value为位置数组的哈希表根据题意模拟即可。

参考代码

  1. class Solution:
  2.     def __init__(self, nums: List[int]):
  3.         self.pos = collections.defaultdict(list)
  4.         for i,num in enumerate(nums):
  5.             self.pos[num].append(i)
  7.     def pick(self, target: int) -> int:
  8.         return random.choice(self.pos[target])

复杂度分析

时间复杂度 O(n) 主要时间复杂度都在建立哈希表的遍历过程。n为数组长度
空间复杂度 O(n) 哈希表的存储

方法二 水塘抽样

思路分析

当遍历到第i个元素的时候有398. 随机数索引 - 图1398. 随机数索引 - 图2的概率将其保留下来。证明过程可以看水塘抽样算法

参考代码

  1. class Solution:
  2.     def __init__(self, nums: List[int]):
  3.         self.nums = nums
  5.     def pick(self, target: int) -> int:
  6.         ans = cnt = 0
  7.         for n,num in enumerate(self.nums):
  8.             if num == target:
  9.                 cnt += 1
  10.                 # 当 cnt = 1 的时候 randrange(cnt)必等于0所以这里必定会走一次
  11.                 if random.randrange(cnt) == 0:
  12.                     ans = n
  14.         return ans

复杂度分析

时间复杂度 O(n) n为数组长度
空间复杂度 O(1)