title

problem link

给定一个包含 [0，n) 中不重复整数的黑名单 blacklist ，写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数。

对它进行优化使其尽量少调用系统方法 Math.random() 。

提示:

1. 1 <= n <= 1000000000
2. 0 <= blacklist.length < min(100000, N)
3. [0, n) 不包含 n ，详细参见 interval notation 。

示例 1：

输入：
["Solution","pick","pick","pick"]
[[1,[]],[],[],[]]
输出：[null,0,0,0]

示例 2：

输入：
["Solution","pick","pick","pick"]
[[2,[]],[],[],[]]
输出：[null,1,1,1]

示例 3：

输入：
["Solution","pick","pick","pick"]
[[3,[1]],[],[],[]]
输出：[null,0,0,2]

示例 4：

输入： 
["Solution","pick","pick","pick"]
[[4,[2]],[],[],[]]
输出：[null,1,3,1]

输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution的构造函数有两个参数，n 和黑名单 blacklist。pick 没有参数，输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

solution

分析

白名单中数的个数为 N - len(B)，那么可以直接在 [0, N - len(B)) 中随机生成整数。我们把所有小于 N - len(B) 且在黑名单中数一一映射到大于等于 N - len(B) 且出现在白名单中的数。这样一来，如果随机生成的整数出现在黑名单中，我们就返回它唯一对应的那个出现在白名单中的数即可。

例如当 N = 6，B = [0, 2, 3] 时，我们在 [0, 3) 中随机生成整数，并将 2 映射到 4，3 映射到 5，这样随机生成的整数就是 [0, 1, 4, 5] 中的一个。

算法

我们将黑名单分成两部分，第一部分 X 的数都小于 N - len(B)，需要进行映射；第二部分 Y 的数都大于等于 N - len(B)，这些数不需要进行映射，因为并不会随机到它们。

我们先用 Y 构造出 W，表示大于等于 N - len(B) 且在白名单中的数，X 和 W 的长度一定是相等的。随后遍历 X 和 W，构造一个映射表（HashMap）M，将 X 和 W 中的数构造一一映射。

在 [0, N - len(B)) 中随机生成整数 a 时，如果 a 出现在 M 中，则将它的映射返回，否则直接返回 a。

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        self.b = blacklist
        self.m = {}
        bset = set(self.b)
        blen = len(self.b)
        wlen = n - blen
        # 白名单
        w = []
        for i in range(wlen, n):
            if i not in bset:
                w.append(i)
        j = 0
        for i in blacklist:
            if i < wlen:
                self.m[i] = w[j]
                j += 1
        self.wlen = wlen

    def pick(self) -> int:
        import random
        r = random.randint(0, self.wlen - 1)
        if r in self.m:
            return self.m[r]
        return r