随机数索引

难度: Medium

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。

实现 Solution 类：

Solution(int[] nums) 用数组 nums 初始化对象。
int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。

示例：

输入
["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⁴
-2³¹ <= nums[i] <= 2³¹ - 1
target 是 nums 中的一个整数
最多调用 pick 函数 10⁴ 次

Submission

运行时间: 76 ms

内存: 20.4 MB

class Solution:

    def __init__(self, nums: List[int]):        
    
        self.length = len(nums)
        self.num = nums
        self.dict = defaultdict(list)


  
    def pick(self, target: int) -> int:
        if target in self.dict:
            n = random.choice(self.dict[target])
            return n
        else:
            for i in range(self.length):
                if self.num[i] == target:
                    self.dict[target].append(i)
            n = random.choice(self.dict[target])
            return n
  




# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)

Explain

该题解采用了哈希表的思路。在初始化时，遍历整个数组，将每个数字出现的索引存储在对应的哈希表中，key为数字，value为该数字出现的所有索引列表。在pick方法中，如果目标数字已经在哈希表中，则直接从对应的索引列表中随机选择一个索引返回；否则，遍历数组，找到目标数字的所有索引，存入哈希表中，然后从索引列表中随机选择一个索引返回。

时间复杂度: O(n)

空间复杂度: O(n)

```python
class Solution:

    def __init__(self, nums: List[int]):        
        # 存储数组长度
        self.length = len(nums)
        # 存储原始数组
        self.num = nums
        # 使用defaultdict初始化哈希表，值为列表类型
        self.dict = defaultdict(list)

    def pick(self, target: int) -> int:
        # 如果目标数字已经在哈希表中，直接从对应的索引列表中随机选择一个索引返回
        if target in self.dict:
            n = random.choice(self.dict[target])
            return n
        else:
            # 否则，遍历数组，找到目标数字的所有索引，存入哈希表中
            for i in range(self.length):
                if self.num[i] == target:
                    self.dict[target].append(i)
            # 从索引列表中随机选择一个索引返回
            n = random.choice(self.dict[target])
            return n
```

Explore

这种做法是基于空间和性能权衡的考虑。在初始化过程中如果直接建立完整的哈希表，那么将需要一次性处理数组中的所有元素，这不仅会增加初始化的时间，还可能导致大量不必要的内存消耗，特别是当数组中的元素种类非常多时。通过延迟加载（即在首次需要时才处理特定数字），可以减少不必要的计算和内存使用，尤其是在实际使用中如果只有少部分数字被频繁查询的场景。

不会引入概率偏差。因为每个索引在哈希表中只被记录一次，且每次随机选择是基于同一列表进行的，这保证了每个索引被选中的概率是均等的，满足均匀随机性要求。只要随机选择函数本身不具偏差，这种方法不会引入额外的概率偏差。

对于极大的数组，这种实现在首次查询任何数字时可能会有较高的延迟，因为需要遍历整个数组以构建哈希表中特定数字的索引列表。然而，一旦索引列表被创建，后续的查询将非常快速。在高频率调用pick方法的场景下，如果大部分数字的索引已经被缓存，则性能会非常好。但如果频繁查询未缓存的数字，则可能导致性能下降，因为每次都需要进行数组遍历。

可以保持均匀随机性。每次pick方法被调用时，都是从存储的索引列表中随机选择一个索引，这些索引列表在创建时就已经包含了目标数字的所有出现位置，且以后不会更改。这确保了每个索引被选中的概率是相等的。只要使用的随机选择方法是公正的，多次调用pick方法都能维持均匀随机性。