0710. Random Pick with Blacklist

题目信息

题号:

0710

难度:

Hard

主题:

随机化、黑名单、等概率抽样

原题:

LeetCode 0710

重点:

抽样范围是 [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。