0710：黑名单中的随机数（★★）

力扣第 710 题

题目

给定一个整数 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 <= 109
• 0 <= blacklist.length <= min(105, n - 1)
• 0 <= blacklist[i] < n
• blacklist 中所有值都 不同
• pick 最多被调用 2 * 104 次

相似问题：

• 0398：随机数索引
• 0528：按权重随机选择
• 1980：找出不同的二进制字符串（1361 分）

分析

#1

• 设黑名单长度 m，那么考虑建立 [0,n-m-1] 和不在黑名单中的数的映射
• 假设 x 映射得到的数是 y，y-x 即是 <=y 的黑名单的个数
• 那么 y 减去 <=y 的黑名单的个数即是原来的 x，这是递增的
• 因此给定 x，可以二分查找到 y
  • 注意为了不定位到黑名单，计算的是 <=y 而不是 <y 的个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        self.A = sorted(blacklist)
        self.n = n
        self.k = n-len(self.A)

    def pick(self) -> int:
        def cal(y):
            return y-bisect_right(self.A,y)

        x = randrange(self.k)
        return bisect_left(range(self.n),x,key=cal)

567 ms

#2

• 还有种直接建立映射的方法
• 注意到 n-m 很大，而 m 较小，该映射中大部分数其实是不变的
• 因此考虑只对变化的数做映射
  • [0,n-m-1] 范围内要变化的数其实就是该范围内黑名单中的数
  • 而映射得到的数其实就是 [n-m,n-1] 范围内不在黑名单中的数
• pick 时，随机选一个 [0,n-m-1] 范围内的数，映射即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        m = len(blacklist)
        vis = set(blacklist)
        A = [x for x in blacklist if x<n-m]
        B = [y for y in range(n-m,n) if y not in vis]
        self.k = n-m
        self.d = dict(zip(A,B))

    def pick(self) -> int:
        x = randrange(self.k)
        return self.d.get(x,x)

87 ms