710. 黑名单中的随机数程序员

题目描述这是 LeetCode 上的 710. 黑名单中的随机数，难度为困难。
Tag : 「前缀和」、「二分」、「离散化」、「随机化」
给定一个整数 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(1065, n - 1)$
$0 <= blacklist[i] < n$
blacklist 中所有值都不同
pick 最多被调用 $2 \times 10^4$ 次

前缀和 + 二分 【710. 黑名单中的随机数】为了方便，我们记 blacklist 为 bs，将其长度记为 m。
问题本质是让我们从 $[0, n - 1]$ 范围内随机一个数，这数不能在 bs 里面。
由于 $n$ 的范围是 $1e9$，我们不能在对范围在 $[0, n - 1]$ 且不在 bs 中的点集进行离散化，因为离散化后的点集大小仍很大。
同时 $m$ 的范围是 $1e5$，我们也不能使用普通的拒绝采样做法，这样单次 pick 被拒绝的次数可能很大。
一个简单且绝对正确的做法是：我们不对「点」做离散化，而利用 bs 数据范围为 $1e5$，来对「线段」做离散化。
具体的，我们先对 bs 进行排序，然后从前往后处理所有的 $bs[i]$，将相邻 $bs[i]$ 之间的能被选择的「线段」以二元组 $(a, b)$ 的形式进行记录（即一般情况下的 $a = bs[i - 1] + 1$，$b = bs[i] - 1$），存入数组 list 中（注意特殊处理一下两端的线段）。
当处理完所有的 $bs[i]$ 后，我们得到了所有可被选择线段，同时对于每个线段可直接算得其所包含的整数点数。
我们可以对 list 数组做一遍「线段所包含点数」的「前缀和」操作，得到 sum 数组，同时得到所有线段所包含的总点数（前缀和数组的最后一位）。
对于 pick 操作而言，我们先在 $[1, tot]$ 范围进行随机（其中 $tot$ 代表总点数），假设取得的随机值为 $val$，然后在前缀和数组中进行二分，找到第一个满足「值大于等于 $val$」的位置（含义为找到这个点所在的线段），然后再利用该线段的左右端点的值，取出对应的点。
代码：

class Solution { List 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 进行排序复杂度为 $O(m\log{m})$；统计所有线段复杂度为 $O(m)$；对所有线段求前缀和复杂度为 $O(m)$。在 pick 操作中：随机后会对所有线段做二分，复杂度为 $O(\log{m})$
空间复杂度：$O(m)$

最后这是我们「刷穿 LeetCode」系列文章的第 No.710 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSou... 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地
本文由mdnice多平台发布