LeetCode 398. 随机数索引题目描述给定一个可能含有重复元素的整数数组要求随机输出给定的数字的索引。你可以假设给定的数字一定存在于数组中。注意数组大小可能非常大使用太多额外空间的解决方案会不通过测试。实现 Solution 类· Solution(int[] nums)用整数数组 nums 初始化对象· int pick(int target)从 nums 中选出一个满足 nums[i] target 的随机索引 i。如果存在多个有效索引每个索引被选中的概率应当相等解法一哈希表预处理推荐思路构造时把每个值对应的所有索引存入 HashMappick 时在对应列表中随机取一个。classSolution{privateMapInteger,ListIntegermap;privateRandomrandom;publicSolution(int[]nums){mapnewHashMap();randomnewRandom();for(inti0;inums.length;i){map.computeIfAbsent(nums[i],k-newArrayList()).add(i);}}publicintpick(inttarget){ListIntegerlistmap.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.numsnums;this.randomnewRandom();}publicintpick(inttarget){intresult-1;intcount0;for(inti0;inums.length;i){if(nums[i]target){count;// 以 1/count 的概率替换结果if(random.nextInt(count)0){resulti;}}}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/krandom.nextInt(k) 0· 之后的每次出现第 k1 到第 m 次都不替换它的概率为(1 - 1/(k1)) · (1 - 1/(k2)) · … · (1 - 1/m) k/m· 最终 iₖ 留下的概率 (1/k) · (k/m) 1/m因此每个 target 索引被选中的概率都是 1/m满足题目要求。建议若不确定测试用例的调用模式优先使用哈希表预处理解法一因为 pick 是 O(1) 的符合大多数测评环境若题目额外限制空间尽量小则选择解法二。
