# 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 次
```
### 前置知识
* 哈希表
* 概率
### 公司
* 暂无
### 思路
题目让我们从 \[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:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
