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个随机的情况下
能找到黑名单映射的白名单的值即可

20221124

• 黑名单白名单重映射方法
• 将离散的名单分为两个有序的集合
• 前面放白名单，后面放黑名单
• 只抽前面的，保证如果抽到黑名单可以映射到一个后面的白名单中
• 优秀快速的白名单随机选取算法