困难

问题描述

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

黑名单映射

假设范围大小为 $n$，$blacklist$ 大小为 $m$，那么可选数字的个数就为 $n - m$。假设在 $[0, n - m)$ 范围内，有 $k$ 个数字在黑名单中，那么在 $[n - m, n)$ 范围内必然也有 $k$ 个数字不在黑名单中，因为 $[n - m, n)$ 大小为 $m$，此范围内在黑名单中的数字个数为 $m - k$，那么不在黑名单的数字个数就是 $m - (m - k) = k$。只需在 $[0, n - m)$ 范围内在黑名单中的数字与在$[n - m, n)$ 范围内中不在黑名单的数字建立映射，随机取数时若随机到黑名单中的数字，则取映射表中的值即可。

/**
 * @param {number} n
 * @param {number[]} blacklist
 */
var Solution = function (n, blacklist) {
  this.map = new Map()
  this.bound = n - blacklist.length
  let last = n - 1
  for (const number of blacklist) {
    if (number >= this.bound) this.map.set(number, -1)
  }
  for (const number of blacklist) {
    if (number < this.bound) {
      while (this.map.has(last)) last--
      this.map.set(number, last--)
    }
  }
}

/**
 * @return {number}
 */
Solution.prototype.pick = function () {
  const idx = ~~(Math.random() * this.bound)
  return this.map.get(idx) || idx
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(n, blacklist)
 * var param_1 = obj.pick()
 */

• 时间复杂度：构造函数复杂度为 $O(m)$，$\text {pick}$ 函数复杂度为 $O(1)$
• 空间复杂度：$O(m)$