1. 问题背景与需求分析

LeetCode 710题"黑名单中的随机数"是一个经典的算法设计问题，要求我们实现一个能够高效生成不在黑名单中的随机数的解决方案。这个问题的实际应用场景非常广泛，比如：

• 游戏开发中需要随机生成不重复的道具ID
• 抽奖系统中需要排除已中奖用户
• 安全系统中需要生成不在黑名单中的会话token

题目给出的具体需求是：设计一个类，初始化时接收整数n和一个黑名单blacklist，然后提供一个pick方法，每次调用时均匀随机返回一个[0, n-1]范围内且不在blacklist中的数字。

2. 直观解法与性能分析

2.1 暴力解法思路

最直观的解法是：

1. 初始化时把不在黑名单中的数字全部存储起来
2. pick时从这个集合中随机选择一个

class Solution { List<Integer> whitelist; Random rand; public Solution(int n, int[] blacklist) { whitelist = new ArrayList<>(); Set<Integer> blackSet = new HashSet<>(); for (int num : blacklist) blackSet.add(num); for (int i = 0; i < n; i++) { if (!blackSet.contains(i)) whitelist.add(i); } rand = new Random(); } public int pick() { return whitelist.get(rand.nextInt(whitelist.size())); } }

2.2 暴力解法的问题

这种方法在n很大而blacklist很小的情况下会浪费大量内存。例如n=1e9，blacklist.size=1e5时：

• 需要存储约1e9个数字
• 初始化时间复杂度O(n)
• 空间复杂度O(n)

显然这种解法无法处理大规模数据。

3. 优化解法设计

3.1 核心思路

我们需要找到一种方法，能够：

1. 不显式存储所有白名单数字
2. 仍然保证每个有效数字被选中的概率均等
3. pick操作时间复杂度尽可能低

3.2 映射方案

可以采用"重映射"的思想：

1. 确定白名单数字的个数M = n - blacklist.size
2. 将[0,M-1]区间内的黑名单数字映射到[M,n-1]区间内的白名单数字
3. pick时在[0,M-1]范围内随机，如果是黑名单数字则返回映射值

3.3 具体实现步骤

1. 收集所有位于[0,M-1]的黑名单数字（记为B）
2. 收集所有位于[M,n-1]的白名单数字（记为W）
3. 建立B到W的一一映射
4. pick时随机k∈[0,M-1]，如果k在映射中则返回映射值，否则返回k

4. Java代码实现

import java.util.HashMap; import java.util.HashSet; import java.util.Random; import java.util.Set; class Solution { private int M; private Random rand; private HashMap<Integer, Integer> map; public Solution(int n, int[] blacklist) { this.rand = new Random(); this.map = new HashMap<>(); // 计算白名单数字的个数 this.M = n - blacklist.length; // 收集所有黑名单数字 Set<Integer> blackSet = new HashSet<>(); for (int num : blacklist) { blackSet.add(num); } // 准备建立映射 int w = M; for (int b : blacklist) { if (b < M) { // 需要被映射的黑名单数字 // 找到一个>=M且不在黑名单中的数字 while (blackSet.contains(w)) { w++; } map.put(b, w); w++; } } } public int pick() { int k = rand.nextInt(M); return map.getOrDefault(k, k); } }

5. 复杂度分析

5.1 时间复杂度

• 构造函数：O(B)，其中B是blacklist的长度
• pick方法：O(1)

5.2 空间复杂度

• O(B)，只需要存储需要映射的黑名单数字及其映射

6. 关键点解析

6.1 映射的正确性

为什么这种映射能保证均匀随机？

• 我们最终只在[0,M-1]范围内随机
• 对于原本就在[0,M-1]的白名单数字，直接返回
• 对于[0,M-1]的黑名单数字，我们将其映射到[M,n-1]的白名单数字
• 这样每个白名单数字都有且只有一个对应的"入口"

6.2 边界情况处理

需要特别注意：

1. blacklist为空的情况
2. blacklist包含所有数字的情况（此时M=0，pick应该报错）
3. n非常大的情况（1e9级别）
4. blacklist中有重复数字的情况（题目已说明无重复）

7. 实际应用中的变种

7.1 动态黑名单

如果黑名单会动态变化，可以考虑：

• 使用平衡二叉搜索树维护白名单区间
• 每次pick时根据区间长度加权随机选择区间

7.2 带权重的随机

如果需要支持不同数字有不同的权重，可以：

• 使用前缀和数组+二分查找
• 或者使用Alias Method等高效算法

8. 常见问题与调试技巧

8.1 映射不完整

调试时常见错误是映射没有覆盖所有需要映射的黑名单数字。检查：

1. 是否正确处理了所有b < M的黑名单数字
2. 是否找到了足够多的[M,n-1]区间的白名单数字

8.2 无限循环风险

在寻找映射目标时，如果n不够大可能导致无限循环。确保：

1. blacklist.length < n
2. 有足够的白名单数字可供映射

8.3 随机性测试

验证随机性是否均匀：

1. 多次调用pick()统计各数字出现频率
2. 使用卡方检验验证均匀性

9. 性能优化建议

9.1 随机数生成优化

对于高频调用的pick()，可以考虑：

1. 重用Random对象而不是每次创建
2. 使用更快的随机数生成器如ThreadLocalRandom

9.2 内存优化

对于极大n的情况：

1. 使用更紧凑的数据结构存储映射
2. 考虑黑名单数字的分布特性，可能可以分段处理

10. 扩展思考

这个问题展示了算法设计中常见的"空间换时间"和"时间换空间"的权衡。类似的技巧还出现在：

• 哈希冲突解决
• 数据库索引设计
• 内存分页管理

理解这种映射思想有助于解决其他需要高效随机访问的问题。比如在游戏开发中生成唯一ID，或者在分布式系统中生成不冲突的请求ID等场景。