算法题：黑名单中的随机数
今天我们来聊一个算法题：黑名单中的随机数。
有时候我们会遇到一些非常奇葩的需求，尤其是在做一些数据结构和算法相关的工作时。这道题的要求听起来简单，但真正做起来却充满了挑战。让我们一起深入剖析。
题目大致意思是这样的：给定一个范围 [0, N-1]，你要设计一个数据结构，能够返回范围内一个不在黑名单中的随机数。具体来说，我们需要一个 Random 类，支持以下方法：
init(int N, int[] blacklist)：初始化一个范围[0, N-1]，并给出一个黑名单blacklist，它包含了一些不能返回的数。pick()：返回一个随机的、未被黑名单包含的数字。
看似简单，但想要做得高效却有一些小技巧需要掌握。简单来说，我们需要做到的是，如何在每次调用 pick() 时，避免把黑名单中的数字返回，而又不做太多重复的计算。
首先，我们可以想到，黑名单中的数字是需要去除的。但问题是，黑名单的大小可能相对较小，而 pick() 的操作可能需要频繁调用。如果每次都去检查是否在黑名单中，那显然效率不高。
那么我们该怎么优化呢？
一种高效的方法是，通过映射来减少不必要的检查。在初始化时，首先将黑名单中的每个数字和一个未被黑名单包含的数字做映射，然后在 pick() 时通过这个映射来避免黑名单中的数字。
我们可以考虑将黑名单中的数字映射到范围 [0, N-1] 之外的部分。假设我们有一个黑名单数组 blacklist，我们可以将 N-1 到 N-1 - k 的数字映射到黑名单中的数字。这样，实际上就避免了每次 pick() 时都去遍历黑名单，而是通过一个映射表直接跳过那些黑名单中的数。
具体代码实现如下：
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class Solution {
private Map<Integer, Integer> blacklistMap;
private Random random;
private int range;
public Solution(int N, int[] blacklist) {
this.random = new Random();
this.range = N - blacklist.length;
this.blacklistMap = new HashMap<>();
// 建立黑名单数字与合法数字的映射关系
for (int b : blacklist) {
blacklistMap.put(b, -1); // 先初始化映射为空
}
int last = N - 1;
for (int b : blacklist) {
if (b >= range) continue; // 黑名单数字大于或等于范围，不需要映射
while (blacklistMap.containsKey(last)) {
last--; // 找到一个合法的数字
}
blacklistMap.put(b, last--);
}
}
public int pick() {
int rand = random.nextInt(range); // 随机生成一个0到range-1之间的数
return blacklistMap.getOrDefault(rand, rand); // 如果rand在黑名单中，返回映射的合法数
}
}
这段代码的核心逻辑是，我们首先建立一个黑名单到合法数字的映射。在 init() 方法中，我们遍历黑名单，如果黑名单中的数字小于范围 range，则通过映射表将它替换为一个合法的数字。然后，在 pick() 方法中，我们随机选择一个数字，如果这个数字是黑名单中的数字，那么就通过映射表获取一个合法的数字。
通过这种方式，我们就能高效地避免每次都去遍历黑名单，提高了性能。
看起来不难吧？其实就是利用了一个巧妙的映射策略。这个问题背后的核心思想就是通过空间换时间。通过额外的空间（我们使用了一个 Map）来存储黑名单与合法数字的映射，从而避免了在每次调用 pick() 时都去查找黑名单的时间开销。
话说回来，像这种“映射替代检查”的方式，在很多实际的算法问题中都能见到。比如，在某些搜索问题中，避免重复计算的策略就可以借用这种思想，先将一些不容易获得的数据进行映射，再通过这个映射直接获得结果。
有时候，我们程序员做的算法题，不仅仅是解决眼前的问题，更是在训练我们思考问题的方式。正如这道题，它考察的不仅是如何避免黑名单中的数字，更重要的是如何优化我们的方法，让原本需要 O(N) 的查找变成了 O(1) 的常数时间操作。加个映射，少些检查，代码效率直线提升！
对了，大家有没有发现？如果黑名单特别大，或者范围特别大的话，虽然我们用了映射减少了复杂度，但实际上，还是需要考虑到空间的开销。你要保证映射表能适应问题的规模，不然可能会变成性能瓶颈。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
