DeepSeek LeetCode 398. 随机数索引 Java实现

LeetCode 398. 随机数索引

题目描述

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

注意：数组大小可能非常大，使用太多额外空间的解决方案会不通过测试。

实现 Solution 类：

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

解法一：哈希表预处理（推荐）

思路：构造时把每个值对应的所有索引存入 HashMap，pick 时在对应列表中随机取一个。

classSolution{privateMap<Integer,List<Integer>>map;privateRandomrandom;publicSolution(int[]nums){map=newHashMap<>();random=newRandom();for(inti=0;i<nums.length;i++){map.computeIfAbsent(nums[i],k->newArrayList<>()).add(i);}}publicintpick(inttarget){List<Integer>list=map.get(target);returnlist.get(random.nextInt(list.size()));}}

复杂度分析

· 构造：时间 O(n)，空间 O(n)
· pick：时间 O(1)，空间 O(1)

解法二：水塘抽样（Reservoir Sampling）

思路：不额外存储索引，遍历数组统计 target 出现次数 count，对第 k 次出现（count = k）以 1/k 的概率替换结果为当前索引。这样可以保证每个 target 索引被选中的概率都是 1/count。

classSolution{privateint[]nums;privateRandomrandom;publicSolution(int[]nums){this.nums=nums;this.random=newRandom();}publicintpick(inttarget){intresult=-1;intcount=0;for(inti=0;i<nums.length;i++){if(nums[i]==target){count++;// 以 1/count 的概率替换结果if(random.nextInt(count)==0){result=i;}}}returnresult;}}

复杂度分析

· 构造：时间 O(1)，空间 O(1)
· pick：时间 O(n)，空间 O(1)

两种解法对比

方案 构造时间 构造空间 pick 时间 适用场景
哈希表 O(n) O(n) O(1) 多次调用 pick
水塘抽样 O(1) O(1) O(n) 空间受限、调用次数少

为什么水塘抽样可行？
假设 target 在数组中出现了 m 次，索引依次为 i₁, i₂, …, iₘ：

· 处理到第 k 个 target 时，result 被替换成 iₖ 的概率是 1/k（random.nextInt(k) == 0）
· 之后的每次出现（第 k+1 到第 m 次）都不替换它的概率为：(1 - 1/(k+1)) · (1 - 1/(k+2)) · … · (1 - 1/m) = k/m
· 最终 iₖ 留下的概率 = (1/k) · (k/m) = 1/m

因此每个 target 索引被选中的概率都是 1/m，满足题目要求。

建议：若不确定测试用例的调用模式，优先使用哈希表预处理（解法一），因为 pick 是 O(1) 的，符合大多数测评环境；若题目额外限制"空间尽量小"，则选择解法二。