710. 黑名单中的随机数

题目描述

这是 LeetCode 上的 「710. 黑名单中的随机数」 ，难度为 「困难」。

Tag : 「前缀和」、「二分」、「离散化」、「随机化」

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist。

设计一种算法，从 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

• Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单  blacklist 的整数
• int pick() 返回一个范围为 且不在黑名单  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

提示:

• blacklist 中所有值都 不同
• pick 最多被调用   次

前缀和 + 二分

为了方便，我们记 blacklist 为 bs，将其长度记为 m。

问题本质是让我们从 范围内随机一个数，这数不能在 bs 里面。

由于 的范围是 ，我们不能在对范围在 且不在 bs 中的点集进行离散化，因为离散化后的点集大小仍很大。

同时 的范围是 ，我们也不能使用普通的拒绝采样做法，这样单次 pick 被拒绝的次数可能很大。

一个简单且绝对正确的做法是：「我们不对「点」做离散化，而利用 bs 数据范围为 ，来对「线段」做离散化」。

具体的，我们先对 bs 进行排序，然后从前往后处理所有的 ，将相邻 之间的能被选择的「线段」以二元组 的形式进行记录（即一般情况下的 ，），存入数组 list 中（注意特殊处理一下两端的线段）。

当处理完所有的 后，我们得到了所有可被选择线段，同时对于每个线段可直接算得其所包含的整数点数。

我们可以对 list 数组做一遍「线段所包含点数」的「前缀和」操作，得到 sum 数组，同时得到所有线段所包含的总点数（前缀和数组的最后一位）。

对于 pick 操作而言，我们先在 范围进行随机（其中 代表总点数），假设取得的随机值为 ，然后在前缀和数组中进行二分，找到第一个满足「值大于等于 」的位置（含义为找到这个点所在的线段），然后再利用该线段的左右端点的值，取出对应的点。

代码：

class Solution {
    List<int[]> list = new ArrayList<>();
    int[] sum = new int[100010];
    int sz;
    Random random = new Random();
    public Solution(int n, int[] bs) {
        Arrays.sort(bs);
        int m = bs.length;
        if (m == 0) {
            list.add(new int[]{0, n - 1});
        } else {
            if (bs[0] != 0) list.add(new int[]{0, bs[0] - 1});
            for (int i = 1; i < m; i++) {
                if (bs[i - 1] == bs[i] - 1) continue;
                list.add(new int[]{bs[i - 1] + 1, bs[i] - 1});
            }
            if (bs[m - 1] != n - 1) list.add(new int[]{bs[m - 1] + 1, n - 1});
        }
        sz = list.size();
        for (int i = 1; i <= sz; i++) {
            int[] info = list.get(i - 1);
            sum[i] = sum[i - 1] + info[1] - info[0] + 1;
        }
    }
    public int pick() {
        int val = random.nextInt(sum[sz]) + 1;
        int l = 1, r = sz;
        while (l < r) {
            int mid = l + r >> 1;
            if (sum[mid] >= val) r = mid;
            else l = mid + 1;
        }
        int[] info = list.get(r - 1);
        int a = info[0], b = info[1], end = sum[r];
        return b - (end - val);
    }
}

• 时间复杂度：在初始化操作中：对 bs 进行排序复杂度为 ；统计所有线段复杂度为 ；对所有线段求前缀和复杂度为 。在 pick 操作中：随机后会对所有线段做二分，复杂度为
• 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 No.710 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地