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