给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。
又是一道等概率的题目。概率是与样本有关的问题。本题中样本是点，一开始总是以面积作为权重，总是通过不了，然后看火鸡们的解答发现是以点作为权重。
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
# self.areas = [(rect[3] - rect[1]) * (rect[2] - rect[0]) for rect in rects]
self.points_num = [(rect[3] - rect[1] + 1) * (rect[2] - rect[0] + 1) for rect in rects]
self.sum_points_num = [0]
for i in range(len(self.points_num)):
if i == 0:
self.sum_points_num.append(self.points_num[0])
else:
self.sum_points_num.append(self.sum_points_num[i] + self.points_num[i])
# print(self.points_num)
# print(self.sum_points_num)
def pick(self) -> List[int]:
max_point_num = self.sum_points_num[-1]
random_rect = random.randint(1, max_point_num)
# print('random_rect:', random_rect)
rect_index = 0
for i in range(len(self.sum_points_num)-1):
if self.sum_points_num[i] < random_rect <= self.sum_points_num[i+1]:
rect_index = i
break
# print('rect_index:', rect_index)
rect = self.rects[rect_index]
# print('rect:', rect)
random_x = random.randint(rect[0], rect[2])
random_y = random.randint(rect[1], rect[3])
# print([random_x, random_y])
return [random_x, random_y]
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
