LeetCode 398. Random Pick Index 解题思路与 Python 实现

问题背景

给定一个可能包含重复元素的整数数组，要求随机输出目标数字的索引。假设目标数字一定存在于数组中，且每个有效索引被选中的概率必须相等。

关键约束：

• 数组规模可能非常大。
• 使用过多额外空间的方案无法通过评测。
• 必须保证随机性，不能总是返回同一个位置。

核心思路

这道题的核心在于如何在保证随机性的前提下平衡空间与时间复杂度。我们通常有两种主流策略：预处理构建索引映射，或者在查询时动态筛选。

方案一：哈希表预存储

如果查询操作非常频繁，而初始化只进行一次，那么预先将每个数字对应的所有索引存入字典是最高效的。这样 pick 操作的时间复杂度可以降到 O(1)。当然，这需要 O(N) 的额外空间来存储索引列表。

import random

class Solution:
    def __init__(self, nums):
        self.d = {}
        for i, v in enumerate(nums):
            if v in self.d:
                self.d[v].append(i)
            else:
                self.d[v] = [i]

    def pick(self, target):
        arr = self.d[target]
        return arr[random.randint(0, len(arr) - 1)]

这里利用 random.randint 从索引列表中均匀采样。实际运行时，这种方案的内存占用会随数据量线性增长，适合内存充足且查询密集的场景。

方案二：列表推导式动态筛选

如果内存受限，或者查询频率不高，我们可以选择在调用 pick 时遍历数组找出所有匹配项。虽然单次查询变慢为 O(N)，但节省了初始化时的空间开销。

import random

class Solution:
    def __init__(self, nums):
        self.nums = nums

    def ():
        idxs = [i  i, num  (.nums)  num == target]
         random.choice(idxs)