当前位置：首页 > news >正文

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

news 2026/5/11 18:15:43

LeetCode 710. 黑名单中的随机数详细题解

问题分析

这道题的核心是：在[0, n-1]范围内随机选择一个不在黑名单中的数字。要求：

pick()方法要等概率返回白名单中的数字
不能直接创建白名单数组（可能太大）
需要优化时间和空间复杂度

解法一：映射法（最优解）

classSolution{privateMap<Integer,Integer>mapping;privateRandomrandom;privateintvalidRange;// 实际有效的随机范围publicSolution(intn,int[]blacklist){mapping=newHashMap<>();random=newRandom();// 将黑名单中的数字存入Set，方便快速查找Set<Integer>blackSet=newHashSet<>();for(intb:blacklist){blackSet.add(b);}// 有效的随机范围是 [0, n - blacklist.length - 1]validRange=n-blacklist.length;// 处理黑名单中的数字// 思路：将 [0, validRange-1] 范围内的黑名单数字，// 映射到 [validRange, n-1] 范围内的白名单数字// 先找出所有在 [validRange, n-1] 范围内的黑名单数字Set<Integer>blackInValidRange=newHashSet<>();for(intb:blacklist){if(b>=validRange){blackInValidRange.add(b);}}// 为 [0, validRange-1] 范围内的黑名单数字建立映射intwhiteIndex=validRange;// 从 validRange 开始找白名单数字for(intb:blacklist){if(b<validRange){// 跳过也在黑名单中的数字while(blackInValidRange.contains(whiteIndex)){whiteIndex++;}// 将黑名单数字映射到白名单数字mapping.put(b,whiteIndex);whiteIndex++;}}}publicintpick(){intrand=random.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.sortedBlacklist=blacklist;this.random=newRandom();this.n=n;}publicintpick(){intrand=random.nextInt(n-sortedBlacklist.length);// 使用二分查找确定随机数需要跳过多少个黑名单数字intleft=0,right=sortedBlacklist.length-1;while(left<=right){intmid=left+(right-left)/2;// mid位置的黑名单数字，前面有mid个黑名单数字// 所以它实际对应的白名单位置是 sortedBlacklist[mid] - midif(sortedBlacklist[mid]-mid<=rand){left=mid+1;}else{right=mid-1;}}// left 表示需要跳过的黑名单数量returnrand+left;}}

时间复杂度：

构造函数：O(m log m)（排序）
pick()：O(log m)

空间复杂度：O(m)

解法三：列表法（简单但空间大）

classSolution{privateList<Integer>whitelist;privateRandomrandom;publicSolution(intn,int[]blacklist){Set<Integer>blackSet=newHashSet<>();for(intb:blacklist){blackSet.add(b);}whitelist=newArrayList<>();for(inti=0;i<n;i++){if(!blackSet.contains(i)){whitelist.add(i);}}random=newRandom();}publicintpick(){intindex=random.nextInt(whitelist.size());returnwhitelist.get(index);}}

时间复杂度：

构造函数：O(n)
pick()：O(1)

空间复杂度：O(n - m)

缺点：当 n 很大时（如 10^9），无法创建这么大的列表

解法四：完整实现（包含边界情况处理）

classSolution{privateMap<Integer,Integer>mapping;privateRandomrandom;privateintvalidRange;publicSolution(intn,int[]blacklist){mapping=newHashMap<>();random=newRandom();// 处理边界情况if(blacklist==null){blacklist=newint[0];}// 排序黑名单，便于处理Arrays.sort(blacklist);// 有效的随机范围validRange=n-blacklist.length;// 将黑名单分成两部分：// 1. 在 [0, validRange-1] 内的黑名单数字（需要映射）// 2. 在 [validRange, n-1] 内的黑名单数字（直接忽略）// 找出后半部分的黑名单数字Set<Integer>highBlack=newHashSet<>();for(intb:blacklist){if(b>=validRange){highBlack.add(b);}}// 为前半部分的黑名单数字建立映射intcurrentHigh=validRange;for(intb:blacklist){if(b<validRange){// 找到下一个不在黑名单中的数字while(highBlack.contains(currentHigh)){currentHigh++;}mapping.put(b,currentHigh);currentHigh++;}}}publicintpick(){intrand=random.nextInt(validRange);// 如果随机到的数字在黑名单中，返回映射值// 否则直接返回原数字Integermapped=mapping.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