题目描述
思路

leetcode - daily - 710. 黑名单中的随机数

September 09, 2021

题目描述

给定一个包含 [0,n) 中不重复整数的黑名单 blacklist ,写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数。

对它进行优化使其尽量少调用系统方法 Math.random() 。

提示:

1 <= n <= 1000000000
0 <= blacklist.length < min(100000, N)
[0, n) 不包含 n ,详细参见 interval notation 。
示例 1:

输入:
["Solution","pick","pick","pick"]
[[1,[]],[],[],[]]
输出:[null,0,0,0]
示例 2:

输入:
["Solution","pick","pick","pick"]
[[2,[]],[],[],[]]
输出:[null,1,1,1]
示例 3:

输入:
["Solution","pick","pick","pick"]
[[3,[1]],[],[],[]]
输出:[null,0,0,2]
示例 4:

输入:
["Solution","pick","pick","pick"]
[[4,[2]],[],[],[]]
输出:[null,1,3,1]
输入语法说明:

输入是两个列表:调用成员函数名和调用的参数。Solution的构造函数有两个参数,n 和黑名单 blacklist。pick 没有参数,输入参数是一个列表,即使参数为空,也会输入一个 [] 空列表。



来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-with-blacklist
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  1. 数据长度以及黑名单长度已知,可以推出 白名单长度 len_white
  2. 为了保证白名单能够随机获取, 可以考虑对 len_white 做文章
  3. 当对 lenwhite 做下标随机时, 随机获取的数 Nums[random(lenwhite)] 可能是白名单,也可能是黑名单
  4. 所以问题关键在与将 Nums[0…len_white] 内的黑名单和 Nums[len_white…n]内的白名单做一一映射

/**
 * @param {number} n
 * @param {number[]} blacklist
 */
var Solution = function(n, blacklist) {
  const len = blacklist.length
  const limit = n - len
  const blackSet = new Set(blacklist)

  let term = []
  for (let i = limit; i < n; i++) {
    if (blackSet.has(i)) {
      blackSet.delete(i)
    } else {
      term.push(i)
    }
  }

  let m = {}, j = 0;

  for (let v of blackSet) {
    if (v < limit) {
      m[v] = term[j++]
    }
  }

  this.limit = limit
  this.map = m
  this.blackSet = blackSet
};

/**
 * @return {number}
 */
Solution.prototype.pick = function() {
  const { limit, map, blackSet } = this

  const randomValue = Math.floor(Math.random() * limit)

  return blackSet.has(randomValue) ? map[randomValue] : randomValue

};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(n, blacklist)
 * var param_1 = obj.pick()
 */
  • 时间复杂度: $O(M)$, M 为黑名单长度
  • 空间复杂度: $O(M)$, M 为黑名单长度

feiker 少年起而行之