LeetCode 398. 随机数索引
题目描述
题意分析
给定一个可能包含重复值的数组，之后可以多次查询目标值
target。每次要随机返回满足nums[i] == target的一个原数组下标；若目标出现多次，每个有效下标被返回的概率必须相同。题目保证每次查询的目标都存在。返回的是下标，不是目标值，也不是它在候选列表中的序号。不同查询重新进行随机选择，允许连续多次碰巧返回同一个下标，不要求轮流、不重复或固定顺序。
解法：哈希表预处理下标
核心思路
[!blue]
数组本身没有更新操作，可以在构造对象时把每个值对应的所有原下标收集到一张哈希表中。
positions[value]保存的列表，就是查询这个值时的全部有效候选，重复值的每次出现都单独登记。查询时先取得目标的下标列表。若列表长度为
m，在整数区间[0, m)中均匀随机选择位置idx，再返回indices[idx]。列表位置与目标在原数组中的出现一一对应，所以每个原下标被选中的概率都是1 / m。这个过程不从整个原数组随机尝试再判断是否命中目标，因此即使目标很少出现，查询也不需要反复重试。代价是构造时扫描一次数组，并保存全部出现位置；之后可重复利用这份索引处理不同目标。
随机发生在每次
pick调用中，不能预先为每个目标只抽取一个位置后永久复用。使用随机库提供的有界均匀取样，也能直接保证范围正确，避免自行把任意随机整数取模带来的负下标或分布偏差。
解题步骤
- 构造时遍历原数组，把下标
i加入positions[nums[i]]。- 查询时取出
positions[target]；题目保证它非空。- 在候选列表长度范围内均匀抽取一个位置。
- 返回该位置保存的原数组下标。
代码实现
class Solution {
// 题目保证查询的 target 一定存在，因此取到下标列表后不需要额外处理空结果。
private final Map<Integer, List<Integer>> positions = new HashMap<>();
public Solution(int[] nums) {
for (int i = 0; i < nums.length; i++) {
positions.computeIfAbsent(nums[i], key -> new ArrayList<>()).add(i);
}
}
public int pick(int target) {
List<Integer> indices = positions.get(target);
// 均匀抽候选列表位置，再映射回原数组下标
int idx = java.util.concurrent.ThreadLocalRandom.current().nextInt(indices.size());
return indices.get(idx);
}
}
import "math/rand"
type Solution struct {
// 题目保证查询的 target 一定存在，因此取到下标列表后不需要额外处理空结果。
positions map[int][]int
}
func Constructor(nums []int) Solution {
positions := make(map[int][]int)
for i, num := range nums {
positions[num] = append(positions[num], i)
}
return Solution{positions: positions}
}
func (s *Solution) Pick(target int) int {
indices := s.positions[target]
// 均匀抽候选列表位置，再映射回原数组下标
idx := rand.Intn(len(indices))
return indices[idx]
}
复杂度分析
- 时间复杂度：构造期望 $O(n)$，每个下标登记一次；每次查询期望 $O(1)$，哈希查找后进行一次有界抽样和数组读取。
- 空间复杂度：$O(n)$，所有候选列表合计保存每个原下标一次。
关键点总结
[!green]
- 同值的不同出现是不同候选，必须完整收集其下标。
- 均匀抽取候选列表的位置，再映射回原下标，就得到等概率结果。
- 预处理用线性空间换取快速查询，每次查询独立重新抽样。
解法二：水塘抽样
核心思路
[!blue]
若不希望额外保存所有下标，可以在每次查询时扫描原数组，只保留一个当前候选
answer和已经遇到的目标数量count。遇到非目标值直接跳过，遇到第count个目标时，以1 / count的概率把答案替换成它的下标。第一处匹配的
count为一，必然被选中。假设处理完前t - 1个候选后，它们各自被保存的概率为1 / (t - 1)；加入第t个候选时，新下标以1 / t被选中，旧候选以(t - 1) / t的概率保留。于是每个旧候选的最终概率为1 / (t - 1) × (t - 1) / t = 1 / t，与新候选相同。这个性质从第一个候选逐步成立，所以扫描结束时，无论目标一共出现多少次，每个匹配下标都有相同机会。代码在
[0, count)均匀取一个整数，只有取到零时替换答案，恰好实现1 / count。构造函数只保留输入数组引用，题目没有修改数组的操作。每次查询重新把计数归零并完成一次扫描，省去线性下标表，但查询时间也从常数变成线性。它适合更在意额外空间的情况，不会同时获得哈希预处理的查询速度。
解题步骤
- 构造时保留原数组，查询时初始化
count = 0、answer = -1。- 扫描数组，非目标值不参与候选计数。
- 每遇到目标，将
count加一；若[0, count)的随机结果为零，就保存当前下标。- 完成全部扫描后返回保存的下标；目标保证存在，所以至少会选中第一处匹配。
代码实现
class Solution {
private final int[] nums;
public Solution(int[] nums) {
this.nums = nums;
}
public int pick(int target) {
int count = 0;
int answer = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != target) {
continue;
}
count++;
if (java.util.concurrent.ThreadLocalRandom.current().nextInt(count) == 0) {
answer = i;
}
}
return answer;
}
}
import "math/rand"
type Solution struct {
nums []int
}
func Constructor(nums []int) Solution {
return Solution{nums: nums}
}
func (s *Solution) Pick(target int) int {
count, answer := 0, -1
for i, num := range s.nums {
if num != target {
continue
}
count++
if rand.Intn(count) == 0 {
answer = i
}
}
return answer
}
复杂度分析
- 时间复杂度：构造为 $O(1)$，只保存引用；每次查询为 $O(n)$，需要检查全部数组元素。
- 空间复杂度：$O(1)$ 额外空间，复用输入数组，只保存候选数量与一个下标，不复制输入。
关键点总结
[!green]
- 第
t个有效候选以1 / t概率替换答案，使所有已见候选继续等概率。- 计数只包含目标值，每次查询都重新计数和抽样。
- 常数额外空间以每次完整扫描为代价，应与预处理方案区分。
易错点总结
[!yellow]
- 每个值只保存一个下标，会让其他出现永远没有被选中的机会。
- 随机上界使用原数组长度，可能超出目标候选列表范围。
- 返回抽到的候选序号，而不是候选序号对应的原数组下标，会返回错误位置。
- 将某次抽样结果缓存后一直返回，不能实现每次重新随机查询。
- 水塘抽样把非目标元素也计入
count，会破坏有效候选之间的等概率关系。- 每次遇到目标都用固定概率替换，较晚出现的下标会获得不同概率；替换概率应是当前候选数的倒数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 382. 链表随机节点 | 中等 | 同样对流式出现的候选做蓄水池抽样，本题只把值等于目标的位置计入候选数。 |