497 非重叠矩形中的随机点（概率）

男娘i 2022-10-04 12:55 154阅读 0赞

**1. 问题描述：**

给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

**提示：**

整数点是具有整数坐标的点。  
矩形周边上的点包含在矩形覆盖的空间中。  
第 i 个矩形 rects \[i\] = \[x1，y1，x2，y2\]，其中 \[x1，y1\] 是左下角的整数坐标，\[x2，y2\] 是右上角的整数坐标。  
每个矩形的长度和宽度不超过 2000。  
1 <= rects.length <= 100  
pick 以整数坐标数组 \[p\_x, p\_y\] 的形式返回一个点。  
pick 最多被调用10000次。

**示例 1：**  
输入:  
\["Solution","pick","pick","pick"\]  
\[\[\[\[1,1,5,5\]\]\],\[\],\[\],\[\]\]  
输出:  
\[null,\[4,1\],\[4,1\],\[3,3\]\]

**示例 2：**  
输入:  
\["Solution","pick","pick","pick","pick","pick"\]  
\[\[\[\[-2,-2,-1,-1\],\[1,0,3,0\]\]\],\[\],\[\],\[\],\[\],\[\]\]  
输出:  
\[null,\[-1,-2\],\[2,0\],\[-2,-1\],\[3,0\],\[-2,-2\]\]  
输入语法的说明：  
输入是两个列表：调用的子例程及其参数。Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles

**2. 思路分析：**

分析题目可以知道这是一道**概率**的问题（生成随机点问题），因为生成的随机点落在矩形中的概率与矩形的面积是成正比的，所以这是一个二维的概率问题，首先我们需要将二维的问题转化为一维的问题，一维的时候可以直接使用随机函数生成随机点，我们可以将每一个矩形的面积作为一个线段，这样矩形面积越大落在该线段的概率就是越大的，所以我们可以维护一个所有矩形面积的前缀和，这样就可以使用二分查找出当前生成的随机点是在一维线段中对应的是哪一段的，找出的这一段对应的就是某一个矩形，这样我们就可以确定在哪一个矩形中生成随机点了，在矩形中生成随机点其实也很简单，因为横坐标与纵坐标是相互独立的所以我们对横纵坐标各自使用随机函数生成随机点即可。

**3. 代码如下：**

from typing import List
    import random
    
    
    class Solution:
        rects, s = None, None
        # s表示面积对应的前缀和方便后面使用二分查找当前的点位于哪一个区域
        n = 0
    
        def __init__(self, rects: List[List[int]]):
            self.rects = rects
            self.n = len(rects)
            s = [0]
            # 维护面积的前缀和
            for rec in rects:
                x = rec[2] - rec[0] + 1
                y = rec[3] - rec[1] + 1
                s.append(s[-1] + x * y)
            self.s = s
    
        def pick(self) -> List[int]:
            s = self.s
            n = self.n
            # 生成1-s范围的随机数
            x = random.randint(1, s[-1])
            # 使用二分查找当前生成的点位于哪一段, 也即对应的是哪一个矩形
            l, r = 1, n
            while l < r:
                mid = l + r >> 1
                if s[mid] >= x:
                    r = mid
                else:
                    l = mid + 1
            # 找出了具体的矩形
            t = self.rects[r - 1]
            # 矩形的长度与宽度
            dx, dy = t[2] - t[0], t[3] - t[1]
            # 在矩形中生成横坐标与纵坐标的随机点
            return [t[0] + random.randint(0, dx), t[1] + random.randint(0, dy)]