非重叠矩形中的随机点

难度: Medium

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 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⁹ <= a_i < x_i <= 10⁹
-10⁹ <= b_i < y_i <= 10⁹
x_i - a_i <= 2000
y_i - b_i <= 2000
所有的矩形不重叠。
pick 最多被调用 10⁴ 次。

Submission

运行时间: 73 ms

内存: 19.8 MB

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.sum = [0]
        for a, b, x, y in rects:
            self.sum.append(self.sum[-1] + (x - a + 1) * (y - b + 1))

    def pick(self) -> List[int]:
        k = randrange(self.sum[-1])
        rectIndex = bisect_right(self.sum, k) - 1
        a, b, _, y = self.rects[rectIndex]
        da, db = divmod(k - self.sum[rectIndex], y - b + 1)
        return [a + da, b + db]

Explain

该题解的思路包括两个主要步骤：首先，在初始化阶段，计算每个矩形包含的整数点数量，并使用前缀和数组来快速计算点的总数。其次，使用随机抽取的方法，根据权重（即矩形覆盖的点的数量）随机选择一个矩形，然后在这个矩形中随机选择一个点。具体实现中，首先生成一个随机数来确定被选中的矩形，然后计算这个随机数落在该矩形的哪个位置。

时间复杂度: O(log n)

空间复杂度: O(n)

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects  # 存储输入的矩形
        self.sum = [0]  # 前缀和数组，用于存储每个矩形内点的累积总数
        for a, b, x, y in rects:
            # 计算每个矩形内的点数，并更新前缀和数组
            self.sum.append(self.sum[-1] + (x - a + 1) * (y - b + 1))

    def pick(self) -> List[int]:
        k = randrange(self.sum[-1])  # 生成一个随机数
        rectIndex = bisect_right(self.sum, k) - 1  # 二分查找确定随机数落在哪个矩形范围内
        a, b, _, y = self.rects[rectIndex]  # 获取被选矩形的坐标
        da, db = divmod(k - self.sum[rectIndex], y - b + 1)  # 计算随机点的相对位置
        return [a + da, b + db]  # 返回随机点的绝对坐标

Explore

对于每个矩形，其由坐标对(a, b)和(x, y)定义，表示矩形的左下角和右上角。矩形内的整数点总数可通过计算两个坐标间的水平和垂直距离来确定。水平方向上的整数点数为`(x - a + 1)`，垂直方向上的整数点数为`(y - b + 1)`。将这两个数值相乘，即得到该矩形内整数点的总数。这是因为每个水平位置上都有`(y - b + 1)`个垂直位置的点。

为防止整数溢出，通常会选择使用更大的整数类型，如在Python中使用`int`类型，该类型可以自动处理大整数。此外，可以通过适当的模运算来确保数值在安全范围内。在极端情况下，如果数据规模非常大，可能需要采用特殊的数据结构或算法来避免溢出。

`bisect_right`函数查找的是元素应该插入的位置，使得序列仍然保持有序。在使用`bisect_right`查找随机数`k`应该插入的位置后，实际上我们得到的是该随机数刚好大于前一个索引的位置，因此需要减去1来得到随机数所在的矩形索引。这确保了即使随机数恰好等于某个矩形的前缀和界限值，也能正确地归类到前一个矩形。

在构造函数中预先计算每个矩形的点数并存储前缀和，是为了优化`pick`函数的效率。这种方法使每次调用`pick`时，只需进行简单的随机数生成和二分查找，而不需要重复计算矩形的点数。这在多次调用`pick`的情况下显著减少了计算量，提高了算法的整体性能。