[2022-06-26]710. 黑名单中的随机数👋哈希表👋数学👋二分查找👋排序👋随机化

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/random-pick-with-blacklist

难度: Hard
标签: 哈希表 数学 二分查找 排序 随机化

[dreamjean]

710. 黑名单中的随机数

Description

Difficulty: 困难

Related Topics: 哈希表, 数学, 二分查找, 排序, 随机化

给定一个整数 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 <= 10⁹
• 0 <= blacklist.length <= min(10⁵, n - 1)
• 0 <= blacklist[i] < n
• blacklist 中所有值都 不同
• pick 最多被调用 2 * 10⁴ 次

Solution

Language: JavaScript

思路：

• 从 [0, n - blacklist.length] 选取一个随便数
• 给黑名单的每个元素设定一个值，记录到哈希表中时略过这些值

/**
 * @param {number} n
 * @param {number[]} blacklist
 */
var Solution = function(n, blacklist) {
    this.bound = n - blacklist.length;
    this.map = new Map();
    const set = new Set(blacklist);

    let i = this.bound;
    for (let num of blacklist) {
        if (num < this.bound) {
            while (set.has(i)) i++;
            
            this.map.set(num, i++);
        }
    }
};

/**
 * @return {number}
 */
Solution.prototype.pick = function() {
    const r = Math.floor(Math.random() * this.bound);
    return this.map.has(r) ? this.map.get(r) : r;
};

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