『LeetCode』710 黑名单中的随机数

题目

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

相似题目

题解

【黑名单中的随机数】简单分类讨论

分类讨论

有两个比较简单的想法可以实现题目要求：

将不在黑名单的数字列出来，然后随机取，但 \(n\) 最大取值 \(10^9\), 不可行
拒绝采样：先不管黑名单随机取值，若取到黑名单的值就抛弃重新取, 但黑名单的数字数量可能很接近 \(n\), 那么拒绝的概率就会很高导致要重复取样很多次，最大期望采样次数为 \(O(n)\)，也无法接受。

注意到题目给出的取值范围，\(n\) 最大 \(10^9\), 但黑名单最多 \(10^5\) 个，因此可以考虑根据数据范围选择上述方案中的较好的一个，记黑名单的长度为 \(m\)。

若 \(m \leq \dfrac{n}{2}\) ,那么选择随机采样，此时最大期望采样次数为 \(2\), 即平均取随机数的次数不超过两次。
若不满足 1 则 \(10 ^ 5 \geq m > \dfrac{n}{2}\), 即 \(n < 2 \times 10^5\), 此范围可以列出所有非黑名单的值，只需 1 次采样。

经提交验证，在 Java, Python 均能达到超过 90% 以上的效率，不过 C++ 效率会比较低。

# Code language: Python
class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        self.r = n
        m = len(blacklist)
        if m <= n / 2:
            self.type = 0 # 拒绝采样
            self.b = set(blacklist)
        else:
            self.type = 1
            self.b = set(range(n)) - set(blacklist)

    def pick(self) -> int:
        if self.type == 0:
            while True:
                val = random.randint(0, self.r - 1)
                if val not in self.b:
                    return val
        else:
            val = self.b.pop()
            self.b.add(val)
            return val

// Code language: Java
class Solution {
    Random rand = new Random();
    boolean type;
    Set<Integer> b;
    int n;
    int[] whitelist;

    public Solution(int n, int[] blacklist) {
        this.n = n;
        int m = blacklist.length;
        if (m <= n / 2)
            type = true;  // 拒绝采样
        else
            type = false;  // 枚举
        b = new HashSet<>();
        
            for (int val : blacklist)
                b.add(val);
        if(!type) {
            whitelist = new int[n - b.size()];
            for (int i = 0, j = 0; i < n; ++i) {
                if (!b.contains(i))
                    whitelist[j++] = i;
            }
        }
    }

    public int pick() {
        if (type) {
            while (true) {
                int val = rand.nextInt(0, n);
                if (!b.contains(val))
                    return val;
            }
        }
        int m = whitelist.length;
        int val = rand.nextInt(0, m);
        return whitelist[val];
    }
}

// Code language: C++
class Solution {
public:
    bool type;
    unordered_set<int> b;
    int n;
    vector<int> whitelist;

    Solution(int n, vector<int>& blacklist) {
        this->n = n;
        int m = blacklist.size();
        if (m <= n / 2)
            type = true; // 拒绝采样
        else
            type = false; // 枚举

        for (int val : blacklist)
            b.emplace(val);
        if (!type) {
            for (int i = 0; i < n; ++i) {
                if (b.find(i) == b.end())
                    whitelist.emplace_back(i);
            }
        }
    }
    
    int pick() {
        if (type) {
            while (true) {
                int val = rand() % n;
                if (b.find(val) == b.end())
                    return val;
            }
        }
        int m = whitelist.size();
        int val = rand() % m;
        return whitelist[val];
    }
};

时间复杂度: 预处理 \(O(m)\), 其中拒绝采样的预处理是 \(O(m)\), 枚举的预处理是 \(O(n)\) 但枚举的情况 \(n, m\) 是一个数量级，所以也可以认为是 \(O(m)\)，pick 函数为 \(O(1)\), 其中拒绝采样期望是 \(O(2)\), 枚举是 \(O(1)\)
空间复杂度: \(O(m)\)

哈希映射

参考官解的做法，实际上可取的值为 \(n - m\) 个，将黑名单的 \(m\) 个数值映射为 \(n - m\) ~ \(n\) 中的数字即可。

通俗的说，我们将 \([0, n - m)\) 中在黑名单的数字拿掉，然后用 \([n - m, n)\) 中不在黑名单中的数字填上，但我们不能列出完整的 \([0, n - m)\) 数组，所以只用哈希表记录那些替换掉的即可。

# Code language: Python
class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        self.m = n - len(blacklist)
        self.st = dict()
        s = set(blacklist)
        x = self.m
        for b in blacklist:
            if b < self.m:
                while x in s:
                    x += 1
                self.st[b] = x
                x += 1

    def pick(self) -> int:
        val = random.randint(0, self.m - 1)
        if val in self.st:
            return self.st[val]
        return val

时间复杂度: 预处理 \(O(m)\), pick 函数为 \(O(1)\)
空间复杂度: \(O(m)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』710 黑名单中的随机数

题目

标签

相似题目

题解

分类讨论

哈希映射