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``,至少存在一个可返回的整数。 自建示例 -------- 多个合法结果等概率: .. code-block:: text 输入: 操作 = ["Solution", "pick", "pick", "pick"] 参数 = [[6, [0,2,5]], [], [], []] 可能输出:[null, 3, 1, 4] 解释:可返回集合为 {1,3,4}。每次调用都只能返回其中一个值,并且 1、3、4 各自的返回概率都必须为 1/3;展示的序列只是众多合法随机结果之一。 只剩一个合法整数: .. code-block:: text 输入: 操作 = ["Solution", "pick", "pick"] 参数 = [[4, [0,1,3]], [], []] 输出:[null, 2, 2] 解释:区间 [0,3] 中只有 2 不在黑名单内,因此每次调用都必须返回 2。