共计 2576 个字符，预计需要花费 7 分钟才能阅读完成。
题目形容
这是 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$ 次
前缀和 + 二分
为了不便，咱们记 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<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进行排序复杂度为 $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 多平台公布
