黑名单中的随机数

难度: Hard

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言内置随机函数的次数。

实现 Solution 类:

Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

示例 1：

输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
                 // 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4

提示:

1 <= n <= 10⁹
0 <= blacklist.length <= min(10⁵, n - 1)
0 <= blacklist[i] < n
blacklist 中所有值都不同
pick 最多被调用 2 * 10⁴ 次

Submission

运行时间: 173 ms

内存: 26.9 MB

class Solution:
    def __init__(self, n: int, blacklist: List[int]):
        m = len(blacklist)
        self.bound = w = n-m
        black =  {b for b in blacklist if b>=self.bound}
        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)
        




# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()

Explain

该题解的思路是将黑名单中小于 n-m 的数映射到 [n-m, n) 的区间内的白名单数，其中 m 为黑名单的长度。这样在随机选取 [0, n-m) 范围内的数时，如果选中的数在黑名单内，就将其映射到对应的白名单数，否则直接返回选中的数。这种做法可以保证在 [0, n-m) 内的数都是等概率被选中的。

时间复杂度: 初始化的时间复杂度为 O(m)，pick 操作的时间复杂度为 O(1)。

空间复杂度: O(min(n, m))

class Solution:
    def __init__(self, n: int, blacklist: List[int]):
        m = len(blacklist)
        self.bound = w = n-m
        # 获取大于等于 bound 的黑名单数
        black =  {b for b in blacklist if b>=self.bound}
        self.b2w = {}
        for b in blacklist:
            if b<self.bound:
                # 将小于 bound 的黑名单数映射到大于等于 bound 的白名单数
                while w in black:
                    w +=1
                self.b2w[b] = w
                w+=1
        

    def pick(self) -> int:
        # 在 [0, bound) 范围内随机选取一个数
        x = randrange(self.bound) 
        # 如果选中的数在黑名单内，则返回其映射的白名单数，否则直接返回选中的数
        return self.b2w.get(x,x)
        




# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()

Explore

在初始化过程中，我首先通过计算 `bound = n - m` 来确定黑名单和非黑名单的分界线。接着，我通过列表推导式 `{b for b in blacklist if b >= self.bound}` 来直接选出所有大于等于 `bound` 的黑名单元素。这个操作确保了只有大于等于 `bound` 的黑名单数被选中并保存在集合 `black` 中，用于后续的映射过程。这样的筛选是直接且有效的，因为它基于集合操作，可以快速完成黑名单元素的分类。

在当前的构建映射过程中，我使用了 `while w in black` 循环来寻找第一个不在黑名单中的白名单数。这种方法确实可以在每次找到一个小于 `bound` 的黑名单数时，顺序查找第一个可用的白名单数。然而，这个方法在黑名单数接近 `bound` 时可能会变得低效，因为每次都需要从 `bound` 开始检查直到找到一个不在黑名单中的数。一个更优的方法是，使用一个排序好的黑名单数组和一个指针，从 `bound` 开始，如果当前位置的数在黑名单中，则指针向右移动，直到找到不在黑名单中的数，这样可以减少不必要的检查。

选择 `while w in black` 循环是为了确保找到的 `w` 值不在黑名单中，以便将黑名单中小于 `bound` 的数映射到这个 `w` 值。确实，这种方法在黑名单数较多且集中在 `bound` 附近时，可能导致性能下降，因为每次寻找非黑名单的 `w` 都可能需要多次循环迭代。为了优化这一点，可以考虑预先计算出所有大于等于 `bound` 的白名单数，然后使用一个更高效的数据结构（如排序数组或哈希表）来快速访问和检查。