1. 问题背景与需求拆解LeetCode 710题黑名单中的随机数是一个经典的算法设计问题。题目要求我们实现一个类能够高效地从[0, n-1]范围内随机返回一个不在黑名单中的数字。具体来说给定整数n和一个无重复元素的blacklist数组需要实现以下功能构造函数Solution(int n, int[] blacklist)初始化随机数生成器pick()每次调用时返回一个均匀随机的有效数字这个问题的难点在于如何高效处理黑名单特别是在n很大而blacklist相对较小的情况下。直接存储所有有效数字会消耗O(n)空间这在n很大时显然不可行。2. 核心算法思路分析2.1 哈希映射重构法最优解采用了一种巧妙的映射策略核心思想是将黑名单数字重映射到白名单区域。具体步骤如下确定白名单数字的个数m n - blacklist.length将所有≥m的黑名单数字收集到一个集合中建立映射关系对于m的黑名单数字将它们映射到一个≥m的非黑名单数字这样我们只需要维护一个大小与blacklist相同的哈希表就能在O(1)时间内完成随机数的生成和校验。2.2 算法正确性证明这种方法的正确性基于以下观察白名单数字分为两部分m的非黑名单数字和≥m的非黑名单数字对于任何随机数r∈[0,m-1]如果r不在黑名单中直接返回否则返回其映射值由于映射保证了每个有效数字被选中的概率相同因此满足均匀随机的要求3. Java实现详解import java.util.HashMap; import java.util.Map; import java.util.Random; class Solution { private final int m; private final Random random; private final MapInteger, Integer map; public Solution(int n, int[] blacklist) { this.m n - blacklist.length; this.random new Random(); this.map new HashMap(); // 记录所有≥m的黑名单数字 SetInteger blacklistAboveM new HashSet(); for (int num : blacklist) { if (num m) { blacklistAboveM.add(num); } } // 建立映射关系 int candidate m; for (int num : blacklist) { if (num m) { while (blacklistAboveM.contains(candidate)) { candidate; } map.put(num, candidate); candidate; } } } public int pick() { int r random.nextInt(m); return map.getOrDefault(r, r); } }3.1 构造函数解析构造函数主要完成三部分工作计算白名单大小m n - blacklist.length收集所有≥m的黑名单数字到集合中为每个m的黑名单数字寻找一个≥m的非黑名单数字作为映射目标注意映射过程使用了一个自增的candidate指针确保每个黑名单数字都能找到唯一的映射目标。3.2 pick()方法解析pick()方法的实现非常简洁生成[0,m-1]范围内的随机数如果该数在映射表中返回其映射值否则直接返回该数这种方法保证了时间复杂度O(1)的pick操作空间复杂度O(B)其中B是blacklist的长度4. 性能优化与边界处理4.1 随机数生成优化在实际应用中可以考虑使用更高质量的随机数生成器如private final ThreadLocalRandom random ThreadLocalRandom.current();这在多线程环境下能提供更好的性能。4.2 边界条件处理需要特别注意以下边界情况n 0时应该抛出异常blacklist包含重复元素时需要去重blacklist长度≥n时无解改进后的构造函数可以添加参数校验public Solution(int n, int[] blacklist) { if (n 0) throw new IllegalArgumentException(n must be positive); // 其余初始化代码... }5. 实际应用场景扩展这种黑名单随机数生成技术在以下场景有实际应用抽奖系统排除某些不符合条件的用户IDAB测试从用户池中随机选取测试组排除已参与其他实验的用户游戏开发随机生成不重复的道具或敌人例如在抽奖系统中可以这样使用int totalUsers 1000000; int[] excludedUsers getExcludedUsers(); // 获取黑名单 Solution raffle new Solution(totalUsers, excludedUsers); int winner raffle.pick(); // 公平随机选出获奖者6. 常见问题与调试技巧6.1 为什么映射要从m开始因为前m个数字中可能有黑名单数字我们需要将它们映射到后面的非黑名单数字。这样可以保证前m个数字中的白名单数字保持不变前m个数字中的黑名单数字被均匀映射到后面的白名单区域6.2 如何处理非常大的n值当n非常大时如1e9算法仍然有效因为空间复杂度只与blacklist大小有关初始化时间与blacklist大小成正比pick()操作始终保持O(1)时间复杂度6.3 调试技巧在开发过程中可以添加验证逻辑public int pick() { int r random.nextInt(m); int result map.getOrDefault(r, r); if (blacklistSet.contains(result)) { throw new IllegalStateException(Generated number is in blacklist!); } return result; }7. 算法变种与扩展思考7.1 加权随机版本如果需要支持不同数字的不同权重可以结合别名方法(alias method)为白名单数字分配权重构建别名表修改pick()方法实现加权随机7.2 动态黑名单如果黑名单可能动态变化可以考虑使用更复杂的数据结构如跳表采用惰性重映射策略牺牲部分时间效率换取动态更新能力7.3 分布式环境实现在分布式系统中可以使用一致性哈希确定节点负责的区间每个节点维护自己的黑名单映射通过协调器保证全局一致性8. 工程实践建议在实际项目中实现类似功能时建议添加日志记录初始化参数和映射关系便于调试性能监控跟踪pick()方法的调用耗时单元测试覆盖各种边界条件文档注释清晰说明算法原理和使用约束示例测试用例Test public void testSolution() { int n 10; int[] blacklist {3, 5, 7, 9}; Solution solution new Solution(n, blacklist); SetInteger results new HashSet(); for (int i 0; i 1000; i) { int num solution.pick(); assertFalse(Arrays.asList(3, 5, 7, 9).contains(num)); results.add(num); } // 验证所有白名单数字都可能被选中 assertEquals(6, results.size()); }9. 与其他随机数问题的对比与普通随机数生成相比这个问题有几个特殊之处范围不连续有效数字可能是不连续的区间静态黑名单初始化后黑名单不变高效查询需要支持高频的pick操作类似问题还包括带权重的随机选择(LeetCode 528)随机数索引(LeetCode 398)随机翻转矩阵(LeetCode 519)10. 个人实现心得在实际编码过程中有几点特别值得注意映射构建顺序先收集≥m的黑名单数字再处理m的部分这个顺序很重要候选数字选择使用while循环寻找可用候选数字比预先生成所有候选更高效随机数种子在测试时固定随机种子便于重现问题一个容易忽略的细节是blacklist可能包含n本身或更大的数字虽然题目保证blacklist中的数字都在[0,n-1]范围内但防御性编程建议添加校验for (int num : blacklist) { if (num n) throw new IllegalArgumentException(Blacklist number out of range); }
