1.题目基本信息

1.1.题目描述

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

请注意 ，整数点是具有整数坐标的点。

实现 Solution 类:

• Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。

• int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

1.2.题目地址

https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/description/

2.解题方法

2.1.解题思路

前缀和+二分查找

2.2.解题步骤

第一步，从self.preSums[-1]个矩阵节点中随机取一个节点标号

第二步，在preSums中二分查找该节点所在结点的位置；找到第一个大于等于index+1的位置，即第一个大于index的位置；维护左右闭区间，最后的l即为第一个大于index的位置

第三步，根据矩阵的标号和矩阵内的位置，求出结点位置

• 3.1.结点在矩阵内的标号

3.解题代码

python3代码

class Solution:
    # 思路：前缀和+二分查找
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        # > 统计rects中各个矩阵的结点数的前缀和
        self.n = len(rects)
        self.preSums = [0]
        for a, b, x, y in rects:
            self.preSums.append(self.preSums[-1] + (x - a + 1) * (y - b + 1))

    def pick(self) -> List[int]:
        # 第一步，从self.preSums[-1]个矩阵节点中随机取一个节点标号
        index = random.randint(0, self.preSums[-1] - 1)
        # 第二步，在preSums中二分查找该节点所在结点的位置；找到第一个大于等于index+1的位置，即第一个大于index的位置；维护左右闭区间，最后的l即为第一个大于index的位置
        l, r = 1, self.n
        while l <= r:
            mid = (r - l) // 2 + l
            if self.preSums[mid] > index:
                r = mid - 1
            else:
                l = mid + 1
        # 第三步，根据矩阵的标号和矩阵内的位置，求出结点位置
        a, b, x, y = self.rects[l - 1]
        # 3.1.结点在矩阵内的标号
        index -= self.preSums[l - 1]
        rows, cols = y - b + 1, x - a + 1
        result = [a + index % cols, b + index // cols]
        return result



# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()

4.执行结果