0497. Random Point in Non-overlapping Rectangles
================================================
题目信息
--------
:题号: 0497
:难度: Medium
:主题: 不重叠矩形、整数坐标点、随机抽样、全局均匀
:原题: `LeetCode 0497 `_
:重点: 矩形边界包含在内、只返回整数点、所有被覆盖整数点概率相同、矩形选择概率取决于点数
题目重述
--------
实现 ``Solution`` 类。构造函数接收若干互不重叠的轴对齐矩形 ``rects``,每个矩形表示为 ``[a, b, x, y]``,其中 ``(a,b)`` 是左下角,``(x,y)`` 是右上角,并且四条边都属于矩形。
``pick()`` 每次随机返回一个被任意矩形覆盖的整数坐标点 ``[px, py]``。所有可选整数点必须具有完全相同的返回概率;因此包含更多整数点的矩形应按点数获得更高的整体概率,而不是让每个矩形等概率。
``rects.length`` 位于 ``[1, 100]``,坐标位于 ``[-10^9, 10^9]``,且 ``a <= x``、``b <= y``。调用 ``pick`` 的次数不超过 ``10^4``。具体单次返回值不可预先确定。
自建示例
--------
两个矩形共覆盖四个整数点:
.. code-block:: text
构造:rects = [[1,1,1,2], [3,0,4,0]]
可选点:(1,1)、(1,2)、(3,0)、(4,0)
调用:pick()
输出:上述四点中的任意一个
解释:四个整数点的理论概率都应为 1/4。
单点矩形:
.. code-block:: text
构造:rects = [[-2,5,-2,5]]
调用:pick()
输出:[-2,5]
解释:矩形只覆盖一个整数坐标点,因此每次调用都必须返回该点。
按整数点数量选择矩形
--------------------
闭区间矩形 ``[a,b,x,y]`` 覆盖的整数点数为 ``(x-a+1)(y-b+1)``。先计算每个矩形的前缀面积(整数点数量),在所有点的总范围内均匀抽取一个序号;前缀和定位到的矩形,其被选中的概率正比于覆盖点数,正好保证全体整数点等概率。
进入矩形后,再分别在横坐标和纵坐标的闭区间内均匀抽取一个整数即可。面积和使用 ``long long``,不能用几何连续面积或让每个矩形等概率替代整数点数量。
C++ 实现
--------
.. code-block:: cpp
class Solution {
std::vector> rectangles;
std::vector prefix;
std::mt19937 generator{std::random_device{}()};
public:
Solution(std::vector>& rects)
: rectangles(rects) {
long long total = 0;
for (const auto& rect : rectangles) {
long long width = static_cast(rect[2]) - rect[0] + 1;
long long height = static_cast(rect[3]) - rect[1] + 1;
total += width * height;
prefix.push_back(total);
}
}
std::vector pick() {
std::uniform_int_distribution choosePoint(
1, prefix.back());
long long serial = choosePoint(generator);
int index = static_cast(std::lower_bound(
prefix.begin(), prefix.end(), serial) - prefix.begin());
const auto& rect = rectangles[index];
std::uniform_int_distribution chooseX(rect[0], rect[2]);
std::uniform_int_distribution chooseY(rect[1], rect[3]);
return {chooseX(generator), chooseY(generator)};
}
};
代码分析
--------
前缀和序号把所有矩形覆盖的整数点拼成一个不重叠的抽样空间,矩形内的每个点又等概率出现,所以任意可选点概率相同。构造函数时间和空间复杂度为 ``O(r)``,每次 ``pick`` 二分定位耗时 ``O(log r)``,额外抽样空间为 ``O(1)``。