共计 2144 个字符，预计需要花费 6 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 497. 非重叠矩形中的随机点 ，难度为 中等。
Tag :「前缀和」、「二分」、「随机化」
给定一个由非重叠的轴对齐矩形的数组 rects，其中 $rects[i] = [a_i, b_i, x_i, y_i]$ 示意 $(a_i, b_i)$ 是第 $i$ 个矩形的左下角点，$(x_i, y_i)$ 是第 $i$ 个矩形的右上角点。
设计一个算法来随机筛选一个被某一矩形笼罩的整数点。矩形周长上的点也算做是被矩形笼罩。所有满足要求的点必须等概率被返回。
在给定的矩形笼罩的空间内的任何整数点都有可能被返回。
请留神，整数点是具备整数坐标的点。
实现 Solution 类:
Solution(int[][] rects)用给定的矩形数组rects初始化对象。int[] pick()返回一个随机的整数点 $[u, v]$ 在给定的矩形所笼罩的空间内。
示例 1：
输出:
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输入:
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]
解释：Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]提醒：
- $1 <= rects.length <= 100$
- $rects[i].length == 4$
- $-10^9 <= a_i < x_i <= 10^9$
- $-10^9 <= b_i < y_i <= 10^9$
- $x_i – a_i <= 2000$
- $y_i – b_i <= 2000$
- 所有的矩形不重叠。
pick最多被调用 $10^4$ 次。
前缀和 + 二分
为了不便，咱们应用 rs 来代指 rects，定义某个矩阵内整数点的数量为「面积」。
一个奢侈的想法是「先随机应用哪个矩形，再随机该矩形内的点」，其中后者是极其容易的，依据矩形特质，只需在该矩形的 XY 坐标范畴内随机即可确保等概率，而前者（随机应用哪个矩形）为了确保是等概率，咱们不能简略随机坐标，而须要联合面积来做。
具体的，咱们能够预处理前缀和数组 sum（前缀和数组下标默认从 $1$ 开始），其中 $sum[i]$ 代表前 $i$ 个矩形的面积之和（即下标范畴 $[0, i – 1]$ 的面积总和），最终 $sum[n]$ 为所有矩形的总面积，咱们能够在 $[1, sum[n]]$ 范畴内随机，假设随机到的值为 $val$，而后利用 sum 数组的具备枯燥性，进行「二分」，找到 $val$ 所在的矩形（每个矩形均会奉献面积，可看做是每个矩形在数轴 $[1, sum[n]]$ 内奉献一段长度为面积的间断段，咱们二分是为了找到点 $val$ 所在的间断段是由哪个矩形所奉献），而后在该矩形中进行随机，失去最终的随机点。
代码：
class Solution {int[][] rs;
int[] sum;
int n;
Random random = new Random();
public Solution(int[][] rects) {
rs = rects;
n = rs.length;
sum = new int[n + 1];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (rs[i - 1][2] - rs[i - 1][0] + 1) * (rs[i - 1][3] - rs[i - 1][1] + 1);
}
public int[] pick() {int val = random.nextInt(sum[n]) + 1;
int l = 0, r = n;
while (l < r) {
int mid = l + r >> 1;
if (sum[mid] >= val) r = mid;
else l = mid + 1;
}
int[] cur = rs[r - 1];
int x = random.nextInt(cur[2] - cur[0] + 1) + cur[0], y = random.nextInt(cur[3] - cur[1] + 1) + cur[1];
return new int[]{x, y};
}
}- 工夫复杂度：令 $n$ 为给定的
rs数组长度。初始化Solution时须要预处理前缀和数组，复杂度为 $O(n)$；每次pick时须要在矩形个数 $n$ 范畴内进行二分，复杂度为 $O(\log{n})$ - 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.497 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
本文由 mdnice 多平台公布
