0497：非重叠矩形中的随机点（★）

力扣第 497 题

题目

给定一个由非重叠的轴对齐矩形的数组 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
• -109 <= ai < xi <= 109
• -109 <= bi < yi <= 109
• xi - ai <= 2000
• yi - bi <= 2000
• 所有的矩形不重叠。
• pick 最多被调用 104 次。

相似问题：

• 0528：按权重随机选择
• 0478：在圆内随机生成点

分析

• 0528 升级版，变成了二维
• 考虑依此将矩形的点映射为连续区间的点，随机之后再转换回去即可
• 为了节省时间，不用实际映射每个点，只映射区间首尾即可
  • 转换回去时，先二分查找属于哪一个矩形
  • 再得到在该矩形中排第几位，转换成坐标即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:

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

    def pick(self) -> List[int]:
        k = randrange(self.A[-1])
        pos = bisect_right(self.A,k)-1
        k -= self.A[pos]
        a,b,x,y = self.rects[pos]
        i,j = divmod(k,(y-b+1))
        return [a+i,b+j]

111 ms