LeetCode 710 黑名单中的随机数

给定一个整数 n 和一个整数黑名单的非重复黑名单数组。 设计一种算法，从 [0， n - 1] 范围内的任何整数中选择不在黑名单上的整数。 任何在上述范围内且不在黑名单黑名单中的整数都应该有相等的返回概率。

优化算法，使其最大程度地减少语言被调用到其内置随机函数的次数。

实现解决方案类：

solution（int n， int blacklist） 初始化整数 n 和列入黑名单的整数。

int pick（） 返回一个范围为 [0， n - 1] 的随机整数，该整数不在黑名单黑名单中。

示例 1：输入。

solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]

输出。 null, 0, 4, 1, 6, 1, 0, 4]

解释。 solution solution = new solution(7, [2, 3, 5]);

solution.pick();返回 0，则 [0,1,4,6] 的任何整数都可以。 请注意，对于每个选择调用，返回 6 的概率必须相等（即概率为 1 4）。

solution.pick();返回 4

solution.pick();返回 1

solution.pick();返回 6

solution.pick();返回 1

solution.pick();返回 0

solution.pick();返回 4

提示：

1 <= n <= 109

0 <= blacklist.length <= min(105, n - 1)
0 <= blacklist[i] 黑名单中的所有值都不同。 
PICK 最多可调用 2 * 104 次

这意味着我们可以选择的数字数是 n - m，其中 m 是黑名单的长度。 我们需要在这个 n-m 中选择一个随机数，并且每个数字都为一个 1 （n-m） 的记录选择。

我们可以随机取一个数字 [0， n-m-1]。

如果此号码不在黑名单中，您可以直接返回。 不难得出结论，此时的概率是1（n-m），如果这个数字在黑名单上，这与标题一致。 我们不能返回它，然后我们可以将其转换为白名单号码。 由于有 m 个黑名单，如果 [0，n-m-1] 范围内有 x 个黑名单，那么 [n-m+1，n-1] 范围内的黑名单是 m - x，[n-m+1，n-1] 范围内的白名单是 x。 则选择黑名单数量的概率为x（n-m），白名单在[n-m+1，n-1]范围内的概率为1 x。 将两者相乘就是白名单中映射到的数字被选中的概率，即汇总为 1 （n-m），我们可以使用哈希表 b2w 来维护这个映射。 其中 key 是 [0，n-m-1] 中黑名单中的数字，value 是随机找到的 [n-m， n-1] 白名单中的数字。

请参阅具体实现**。

从黑名单到白名单的映射数字 语言支持： python3python3 代码：

class solution: def __init__(self, n: int, blacklist: list[int]):m = len(blacklist) self.bound = w = n - m black = self.b2w = {}for b in blacklist: if b < self.bound: while w in black: w += 1 self.b2w[b] = w w += 1 def pick(self) -int: x = randrange(self.bound) return self.b2w.get(x, x)

设 n 为黑名单长度。

时间复杂度：$o（n）$Space复杂度：$o（n）$