0710. Random Pick with Blacklist¶
题目信息¶
- 题号:
0710
- 难度:
Hard
- 主题:
随机化、黑名单、等概率抽样
- 原题:
- 重点:
抽样范围是
[0, n - 1]中未被拉黑的整数;每个合法整数在每次pick中必须等概率返回,黑名单按值排除且元素互不相同
题目重述¶
实现 Solution 类。构造函数接收正整数 n 和整数数组 blacklist,其中 blacklist 的元素互不相同,并且都位于 [0, n - 1]。这些值构成固定黑名单。
每次调用 pick() 时,必须随机返回区间 [0, n - 1] 内一个不在黑名单中的整数。所有未被拉黑的整数在每次调用中都应具有相同的返回概率。不同调用得到的具体结果可以不同,题目还要求尽量减少对语言内置随机函数的调用次数。
1 <= n <= 10^9,0 <= blacklist.length <= min(10^5, n - 1),pick 最多调用 2 * 10^4 次。由于黑名单长度至多为 n - 1,至少存在一个可返回的整数。
自建示例¶
多个合法结果等概率:
输入:
操作 = ["Solution", "pick", "pick", "pick"]
参数 = [[6, [0,2,5]], [], [], []]
可能输出:[null, 3, 1, 4]
解释:可返回集合为 {1,3,4}。每次调用都只能返回其中一个值,并且 1、3、4 各自的返回概率都必须为 1/3;展示的序列只是众多合法随机结果之一。
只剩一个合法整数:
输入:
操作 = ["Solution", "pick", "pick"]
参数 = [[4, [0,1,3]], [], []]
输出:[null, 2, 2]
解释:区间 [0,3] 中只有 2 不在黑名单内,因此每次调用都必须返回 2。