leetcode：710. 黑名单中的随机数【映射思维】

分析

我们先给一个界限bound 我们希望所有黑名单都可以映射到bound（包括）之后的位置
如果黑名单本来就在bound后面，我们直接把它放入black中
然后遍历其余黑名单，如果发现，它在bound前面
我们从bound的值开始，开始逐个往后遍历，找到第一个非黑名单的位置w
然后令b2w[b] = w这样就完成了黑名单到白名单的映射
然后最后使用随机出一个[0, bound - 1]的数
如果没有映射，说明它就是白名单；如果有隐射，找到其对应的白名单即可

ac code

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:
                # 找到后面中的空位
                while w in black:
                    w += 1
                # 把当前的黑名单 映射 给 对应位置的白名单
                self.b2w[b] = w
                # 下一个位置
                w += 1
        #print(self.b2w)

    def pick(self) -> int:
        x = randrange(self.bound) # 不含右端点，从0开始，步长为1
        #x = randint(0, self.bound - 1)
        return self.b2w.get(x, x) # 如果不是黑名单，就选自己；否则选映射的白名单

总结

黑名单映射的方法，使得按照前bound个随机的情况下
能找到黑名单映射的白名单的值即可