0710. 黑名单中的随机数

题目地址(710. 黑名单中的随机数)

https://leetcode.cn/problems/random-pick-with-blacklist/

题目描述

给定一个整数 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 次

前置知识

• 哈希表

• 概率

公司

• 暂无

思路

题目让我们从 [0, n-1] 随机选一个数，且要求不能是在 blacklist 中，且要求所有数被选中的概率相等。

也就是说我们可以选择的数字的个数为 n - m，其中 m 为 blacklist 的长度。我们需要在这 n - m 中选择一个随机的数，每个数被选中的记录都是 1/(n-m)。

我们可以随机一个 [0, n-m-1] 的数字。

• 如果这个数不在黑名单，直接返回即可。 不难得出，此时的概率是 1/(n-m)，符合题意

• 如果这个数在黑名单。我们不能返回，那么我们可以将其转化为一个白名单的数。 由于黑名单一共有 m 个，假设在 [0,n-m-1]范围内的黑名单有 x 个，那么[n-m+1,n-1] 范围的黑名单就是 m - x，同时在 [n-m+1,n-1] 范围的白名单就是 x。那么其实选中的是黑名单的数的概率就是 x/(n-m)，我们随机找 [n-m+1,n-1] 范围的白名单概率是 1/x。二者相乘就是映射到的白名单中的数被选中的概率，即 1/(n-m)

综上，我们可以使用哈希表 b2w 维护这种映射关系。其中 key 为 [0,n-m-1] 中的黑名单中的数，value 为随机找的一个 [n-m, n-1] 的白名单中的数。

具体实现看代码。

关键点

• 将黑名单中的数字映射到白名单

代码

• 语言支持：Python3

Python3 Code:

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)

复杂度分析

令 n 为 blacklist 长度。

• 时间复杂度：$O(n)$

• 空间复杂度：$O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。