当前位置：网站首页>710. 黑名单中的随机数

710. 黑名单中的随机数

2022-06-26 12:33:00 【宫水三叶的刷题日记】

题目描述

这是 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);
    }
}