DeepSeek LeetCode 710. 黑名单中的随机数 public Solution(int n, int[] blacklist) Java实现

LeetCode 710. 黑名单中的随机数 详细题解问题分析这道题的核心是在[0, n-1]范围内随机选择一个不在黑名单中的数字。要求pick()方法要等概率返回白名单中的数字不能直接创建白名单数组可能太大需要优化时间和空间复杂度解法一映射法最优解classSolution{privateMapInteger,Integermapping;privateRandomrandom;privateintvalidRange;// 实际有效的随机范围publicSolution(intn,int[]blacklist){mappingnewHashMap();randomnewRandom();// 将黑名单中的数字存入Set方便快速查找SetIntegerblackSetnewHashSet();for(intb:blacklist){blackSet.add(b);}// 有效的随机范围是 [0, n - blacklist.length - 1]validRangen-blacklist.length;// 处理黑名单中的数字// 思路将 [0, validRange-1] 范围内的黑名单数字// 映射到 [validRange, n-1] 范围内的白名单数字// 先找出所有在 [validRange, n-1] 范围内的黑名单数字SetIntegerblackInValidRangenewHashSet();for(intb:blacklist){if(bvalidRange){blackInValidRange.add(b);}}// 为 [0, validRange-1] 范围内的黑名单数字建立映射intwhiteIndexvalidRange;// 从 validRange 开始找白名单数字for(intb:blacklist){if(bvalidRange){// 跳过也在黑名单中的数字while(blackInValidRange.contains(whiteIndex)){whiteIndex;}// 将黑名单数字映射到白名单数字mapping.put(b,whiteIndex);whiteIndex;}}}publicintpick(){intrandrandom.nextInt(validRange);// 如果随机到的数字在黑名单中返回映射值// 否则直接返回原数字returnmapping.getOrDefault(rand,rand);}}时间复杂度构造函数O(m)m 是黑名单长度pick()O(1)空间复杂度O(m)解法二二分查找法classSolution{privateint[]sortedBlacklist;privateRandomrandom;privateintn;publicSolution(intn,int[]blacklist){Arrays.sort(blacklist);this.sortedBlacklistblacklist;this.randomnewRandom();this.nn;}publicintpick(){intrandrandom.nextInt(n-sortedBlacklist.length);// 使用二分查找确定随机数需要跳过多少个黑名单数字intleft0,rightsortedBlacklist.length-1;while(leftright){intmidleft(right-left)/2;// mid位置的黑名单数字前面有mid个黑名单数字// 所以它实际对应的白名单位置是 sortedBlacklist[mid] - midif(sortedBlacklist[mid]-midrand){leftmid1;}else{rightmid-1;}}// left 表示需要跳过的黑名单数量returnrandleft;}}时间复杂度构造函数O(m log m)排序pick()O(log m)空间复杂度O(m)解法三列表法简单但空间大classSolution{privateListIntegerwhitelist;privateRandomrandom;publicSolution(intn,int[]blacklist){SetIntegerblackSetnewHashSet();for(intb:blacklist){blackSet.add(b);}whitelistnewArrayList();for(inti0;in;i){if(!blackSet.contains(i)){whitelist.add(i);}}randomnewRandom();}publicintpick(){intindexrandom.nextInt(whitelist.size());returnwhitelist.get(index);}}时间复杂度构造函数O(n)pick()O(1)空间复杂度O(n - m)缺点当 n 很大时如 10^9无法创建这么大的列表解法四完整实现包含边界情况处理classSolution{privateMapInteger,Integermapping;privateRandomrandom;privateintvalidRange;publicSolution(intn,int[]blacklist){mappingnewHashMap();randomnewRandom();// 处理边界情况if(blacklistnull){blacklistnewint[0];}// 排序黑名单便于处理Arrays.sort(blacklist);// 有效的随机范围validRangen-blacklist.length;// 将黑名单分成两部分// 1. 在 [0, validRange-1] 内的黑名单数字需要映射// 2. 在 [validRange, n-1] 内的黑名单数字直接忽略// 找出后半部分的黑名单数字SetIntegerhighBlacknewHashSet();for(intb:blacklist){if(bvalidRange){highBlack.add(b);}}// 为前半部分的黑名单数字建立映射intcurrentHighvalidRange;for(intb:blacklist){if(bvalidRange){// 找到下一个不在黑名单中的数字while(highBlack.contains(currentHigh)){currentHigh;}mapping.put(b,currentHigh);currentHigh;}}}publicintpick(){intrandrandom.nextInt(validRange);// 如果随机到的数字在黑名单中返回映射值// 否则直接返回原数字Integermappedmapping.get(rand);returnmapped!null?mapped:rand;}}/** * Your Solution object will be instantiated and called as such: * Solution obj new Solution(n, blacklist); * int param_1 obj.pick(); */解法对比解法时间复杂度空间复杂度优点缺点映射法O(m) / O(1)O(m)最优解pick O(1)实现稍复杂二分法O(m log m) / O(log m)O(m)空间效率好pick O(log m)列表法O(n) / O(1)O(n-m)实现最简单n 很大时不可行核心思路详解问题本质在[0, n-1]中随机选数排除黑名单关键观察总共有n - blacklist.length个白名单数字我们可以将随机范围缩小到[0, n - blacklist.length - 1]将黑名单中的数字映射到后半部分的白名单数字映射法原理范围划分 [0, validRange-1] | [validRange, n-1] 随机选择范围 | 映射目标范围 黑名单数字分为两类 - 在左边的需要映射到右边 - 在右边的已经被排除不需要映射例子说明n 6, blacklist [0, 2, 3] validRange 3 (6 - 3 3) 映射 0 (左边黑名单) - 3 (右边第一个白名单) 2 (左边黑名单) - 4 (右边第二个白名单) 3 (左边黑名单) - 5 (右边第三个白名单) 最终 pick(0) - 映射到 3 pick(1) - 直接返回 1白名单 pick(2) - 映射到 4边界情况处理空黑名单直接返回随机数黑名单包含所有数字validRange 0pick 返回 -1 或抛出异常n 很大确保不使用 O(n) 空间黑名单未排序需要排序或使用 HashSet面试建议首选解法映射法解法一解释思路先说明不能创建白名单数组的原因空间限制然后解释如何通过映射来解决问题优化点说明为什么要将黑名单分成两部分处理边界情况主动提及要考虑的边界情况