LeetCode 497题 “Random Point in Non-overlapping Rectangles” 是一个中等难度的题目，主要考察的是随机算法和几何知识。题目要求在一个由多个不重叠矩形组成的区域中随机选取一个点。
题目描述
给定一个由多个不重叠矩形组成的列表 rects，每个矩形由其左下角和右上角的坐标表示，即 rects[i] = [x1, y1, x2, y2]，其中 (x1, y1) 是左下角的坐标，(x2, y2) 是右上角的坐标。
你需要实现一个 Solution 类，包含以下方法：
Solution(rects)：用给定的矩形列表初始化对象。pick()：随机选取一个点，返回这个点的坐标。
示例
输入:
["Solution", "pick", "pick", "pick"]
[[[[1,1,5,5]]], [], [], []]
输出:
[null, [4,1], [4,1], [3,3]]
解题思路
-
初始化（
Solution构造函数）：- 计算每个矩形的面积。
- 累积每个矩形的面积，以便后续使用。
-
随机选取点（
pick方法）：- 根据累积的面积随机选择一个矩形。
- 在选中的矩形内随机选择一个点。
详细实现
import random
class Solution: def init(self, rects): self.rects = rects self.areas = [] self.total_area = 0
# 计算每个矩形的面积并累积
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]示例使用
rects = [[1,1,5,5]]
solution = Solution(rects)
print(solution.pick()) # 输出可能是 [4,1], [3,3] 等
解释
-
构造函数
__init__：self.rects存储输入的矩形列表。self.areas存储每个矩形的累积面积。self.total_area存储所有矩形的总面积。
-
pick方法：rand_area是一个在[1, total_area]范围内的随机数。- 通过遍历
self.areas找到包含rand_area的矩形。 - 在选中的矩形内随机生成一个点的坐标。
复杂度分析
-
时间复杂度：
- 构造函数：
O(N)，其中N是矩形的数量。 pick方法：O(N)，因为需要遍历self.areas找到对应的矩形。
- 构造函数：
-
空间复杂度：
O(N)，用于存储矩形的累积面积。
这个实现确保了每个点被选中的概率与其所在矩形的面积成正比，符合题目要求。