给定一个可能含有 重复元素 的整数数组
nums。实现
int pick(int target) : 随机的输出一个值等于给定目标值target的索引。例
- 数组
nums= [1, 2, 3, 3, 3]。
- 如果目标值是 1，我们只能输出 0。
- 但如果给定的目标值是 3，我们要等概率的输出 2, 3, 4。
你可以假设给定的数字一定存在于数组中。
示例：
提示：
1 <= nums.length <= 2 * 104
231 <= nums[i] <= 231 - 1
target是nums中的一个整数
- 最多调用
pick函数104次
解法一：哈希表预处理
给定一个可能包含重复元素的数组
nums，实现 pick(target)，随机返回一个满足 nums[i] == target 的索引，并且所有满足条件的索引被返回的概率必须相等。这道题的核心是：如果
target 出现了多次，如何保证每个索引被选中的概率完全相同？比如
nums = [1, 2, 3, 3, 3]调用
pick(3)，随机返回索引 2, 3 或者 4 之一。并且每个索引都应该以 1/3 的概率返回。最直接的做法是在构造函数里遍历一遍数组，把每个数字对应的所有索引都存起来，方便后续反复查询。
这样每次调用
pick(target) 时，不再扫描整个数组，而是只需要拿到 target 对应的索引列表，然后从里面随机选一个即可。复杂度分析
- 时间复杂度
构造函数：
O(n)，因为需要遍历整个数组一次。pick(target)： O(1)。因为random.choice 从列表中随机取一个元素是常数时间。- 空间复杂度是
O(n) - 构造函数中所有索引都会被存进哈希表。
这个解法适合
pick 会被频繁调用的场景。一次建表，多次查询，查询速度非常快。解法二：Reservoir Sampling
如果数组非常大，或者我们不想额外存下所有索引，哈希表预处理就不一定合适。此时可以用 水塘抽样。
这题其实是水塘抽样里最经典的
k = 1 场景：从未知数量的候选项中，等概率抽取一个。做法是：扫描数组，假设当前已经遇到了
count 个 target，以 1/count 的概率用当前这个 target 索引替换掉之前的答案。这样，即使我们不知道 target 总共出现多少次，扫描结束后，每个 target 索引仍然会以相同概率被选中。
为什么这样做是对的？
- 当我们第一次遇到 target 时，当前只有一个候选索引，所以必须选它，概率是
1。
- 当遇到第二个 target 时，我们用
1/2的概率选新的索引，保留旧答案的概率就成了1 - 1/2
于是两个索引概率都是
1/2。- 当遇到第三个 target 时，我们用
1/3的概率选第三个索引，
前两个索引的概率都会变成：
1/2 * (1 - 1/3) = 1/3所以三个索引最终都是
1/3。以
nums = [1, 2, 3, 3, 3]，target = 3 为例：- 扫描到第一个
3时，count = 1，它一定被选中，答案是索引2。
- 扫描到第二个
3时，count = 2，用1/2的概率把答案替换成索引3；
- 扫描到第三个
3时，count = 3，再用1/3的概率把答案替换成索引4。
最终索引
2、3、4 被保留下来的概率都会是 1/3。复杂度分析
- 时间复杂度
- 构造函数：
O(1) pick(target)：O(n)，每次都需要扫描整个数组。
- 空间复杂度：
O(1) - 不额外存每个数字的索引列表。
- 每次
pick(target)只使用ans和count两个变量。
这个解法适合数组很大、内存敏感，或者只调用少量
pick 的场景。总结
这题要求随机返回
target 的一个索引，并且如果 target 出现多次，每个合法索引必须等概率返回。有两种解法：
- 哈希表预处理：提前存下每个数字出现过的所有索引，查询时随机选一个。
- 是典型的 space-time tradeoff：多花空间，换更快查询。
- 适合
pick调用很多次的场景；
- 水塘抽样 Reservoir Sampling：不额外存索引，每次
pick都扫描数组，用概率更新答案。 - 是典型的 streaming algorithm：即使不知道 target 最终会出现多少次，也能在一次扫描中保持均匀随机。
- 适合数组很大、希望节省空间，或者数据是流式输入的场景。
方法 | 构造时间 | pick(target) 时间 | 额外空间 | 适用场景 |
哈希表预处理 | O(n) | O(1) | O(n) | pick 调用很多次 |
水塘抽样 | O(1) | O(n) | O(1) | 数组很大、空间敏感、流式场景 |
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-398-随机数索引
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 300] 最长递增子序列
下一篇
[Leetcode 403] 青蛙过河