LeetCode 497题 “Random Point in Non-overlapping Rectangles” 是一个中等难度的题目，主要考察的是随机算法和几何知识。题目要求在一个由多个不重叠矩形组成的区域中随机选取一个点。

题目描述

给定一个由多个不重叠矩形组成的列表 rects，每个矩形由其左下角和右上角的坐标表示，即 rects[i] = [x1, y1, x2, y2]，其中 (x1, y1) 是左下角的坐标，(x2, y2) 是右上角的坐标。

你需要实现一个 Solution 类，包含以下方法：

1. Solution(rects)：用给定的矩形列表初始化对象。
2. pick()：随机选取一个点，返回这个点的坐标。

示例

输入: ["Solution", "pick", "pick", "pick"] [[[[1,1,5,5]]], [], [], []] 输出: [null, [4,1], [4,1], [3,3]]

解题思路

1. 初始化（Solution 构造函数）：
   • 计算每个矩形的面积。
   • 累积每个矩形的面积，以便后续使用。
2. 随机选取点（pick 方法）：
   • 根据累积的面积随机选择一个矩形。
   • 在选中的矩形内随机选择一个点。

详细实现

import random

    # 计算每个矩形的面积并累积
    for x1, y1, x2, y2 in rects:
        area = (x2 - x1 + 1) * (y2 - y1 + 1)
        self.total_area += area
        self.areas.append(self.total_area)

def pick(self):
    # 随机选择一个点
    rand_area = random.randint(1, self.total_area)

    # 找到包含该随机点的矩形
    idx = 0
    while rand_area > self.areas[idx]:
        idx += 1

    # 在选中的矩形内随机选择一个点
    x1, y1, x2, y2 = self.rects[idx]
    rand_x = random.randint(x1, x2)
    rand_y = random.randint(y1, y2)

    return [rand_x, rand_y]

print(solution.pick()) # 输出可能是 [4,1], [3,3] 等

解释

1. 构造函数 __init__：
   • self.rects 存储输入的矩形列表。
   • self.areas 存储每个矩形的累积面积。
   • self.total_area 存储所有矩形的总面积。
2. pick 方法：
   • rand_area 是一个在 [1, total_area] 范围内的随机数。
   • 通过遍历 self.areas 找到包含 rand_area 的矩形。
   • 在选中的矩形内随机生成一个点的坐标。

复杂度分析

• 时间复杂度：
  • 构造函数：O(N)，其中 N 是矩形的数量。
  • pick 方法：O(N)，因为需要遍历 self.areas 找到对应的矩形。
• 空间复杂度：O(N)，用于存储矩形的累积面积。

这个实现确保了每个点被选中的概率与其所在矩形的面积成正比，符合题目要求。