部门裁走了两个人，一个月薪15000，一个月薪18000，工作都交接给我，我提一嘴涨薪领导还说我太贪心……

最近在刷算法题的时候，看到一道挺有意思的题目：黑名单中的随机数。

题目的描述大概是这样的：给定一个范围 [0, N-1]，你要在这个范围内随机生成一个数字，不过这个范围内有些数字是“黑名单”，你不能选择这些黑名单上的数字。也就是说，你需要设计一个方法来返回一个在 [0, N-1] 范围内的随机数，但不包括黑名单中的数字。

比如，假设 N = 10，黑名单是 [2, 5, 7]，那么你可以随机选一个 [0, 1, 3, 4, 6, 8, 9] 中的数字。就这么简单？

虽然表面看起来没啥难度，但如何高效地处理这个问题，特别是在黑名单很大的时候，就得好好动动脑筋了。让我们从程序员的角度，来看看这个题怎么做。

思路

首先，我们需要用一个映射来排除黑名单中的数字。一个常见的想法是把黑名单中的数字存进一个集合（set），然后每次生成随机数时，判断它是否在黑名单里。如果在黑名单中，就重新生成直到碰到不在黑名单的数字。

问题来了：这样做的时间复杂度是多少？每次都要判断是否在黑名单，显然这样会浪费大量时间，尤其是当 N 非常大的时候。

所以，咱们得想个聪明的办法。你可能会想，能不能通过一些数学技巧减少计算量呢？答案是：可以！

优化方案

要解决这个问题，我们可以通过“映射”和“随机数重新映射”来提高效率。基本思路是这样的：

1. 将黑名单中的数字从可能的值中移除。
2. 然后把剩下的数字映射成一个新的随机数空间。
3. 利用这个新的空间进行随机数的生成。

具体来说，我们可以使用一个字典 blacklist_map 来记录黑名单中的数字和他们的“合法替代数字”之间的映射。这样，我们就可以把黑名单中的数字通过一个映射转换为合法的数字。

代码实现

下面是一个实现的例子。假设 N 和 blacklist 是我们输入的范围和黑名单，下面这个代码展示了如何通过映射和重新生成随机数来实现：

import random

classSolution:
def__init__(self, N, blacklist):
        self.N = N
        self.blacklist = set(blacklist)

# 创建映射字典
        self.blacklist_map = {}
        self.available = []

# 处理黑名单
        blacklist_idx = 0
for num in range(N - len(blacklist), N):
if num notin self.blacklist:
                self.available.append(num)
else:
                self.blacklist_map[num] = self.available[blacklist_idx]
                blacklist_idx += 1

defpick(self):
# 从不在黑名单中的数字范围中选一个
        pick_num = random.randint(0, self.N - len(self.blacklist) - 1)
if pick_num in self.blacklist_map:
return self.blacklist_map[pick_num]
return pick_num

代码解析

1. **构造函数 __init__(self, N, blacklist)**：

• 我们首先将黑名单转成一个集合，self.blacklist，这样查询黑名单是否包含某个数字会非常高效。
• 然后创建一个字典 self.blacklist_map 来记录黑名单数字与合法替代数字的映射关系。简单来说，blacklist_map[num] 的作用是把黑名单中的 num 替换成一个不在黑名单中的数字。
• 我们也准备一个 self.available 列表来存储不在黑名单中的数字，供随机选择时使用。

• 使用 random.randint(0, N - len(self.blacklist) - 1) 来生成一个随机数 pick_num，范围是 [0, N - len(self.blacklist) - 1]，即排除了黑名单的数字。
• 如果 pick_num 在黑名单中，我们通过 blacklist_map 替换成对应的合法数字。如果 pick_num 不在黑名单中，就直接返回这个数字。

复杂度分析

• 初始化时，我们遍历黑名单并进行映射操作，时间复杂度为 O(K)，其中 K 是黑名单的大小。
• 每次调用 pick 方法时，时间复杂度是 O(1)，因为我们只是进行一个常数时间的随机选择和查找。

这样一来，整个算法在处理黑名单很大的情况下也能保持高效。

总结

这道题看似简单，但在黑名单很大的情况下，直接用暴力方法会非常低效。通过巧妙地使用映射和随机数重新映射，我们能有效地提高算法的效率。希望今天的分享能帮到你，如果你在面试中遇到类似的题目，不妨试试看这个方法。至于我，明天可能又要继续刷题了，不知道会碰到啥新的黑科技 😄