题目描述
题目链接:497. Random Point in Non-overlapping Rectangles
Given a list of non-overlapping axis-aligned rectangles
rects
, write a functionpick
which randomly and uniformily picks an integer point in the space covered by the rectangles.Note: 1.An integer point is a point that has integer coordinates. 2.A point on the perimeter of a rectangle is included in the space covered by the rectangles. 3.
i
th rectangle =rects[i] = [x1,y1,x2,y2]
, where[x1, y1]
are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner. 4.length and width of each rectangle does not exceed2000
. 5.1 <= rects.length <= 100
6.pick return a point as an array of integer coordinates[p_x, p_y]
7.pick
is called at most10000
times.
例子
例子 1
Input:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:[null,[4,1],[4,1],[3,3]]
例子 2
Input:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output:[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
Explanation of Input Syntax
The input is two lists: the subroutines called and their arguments. Solution
’s constructor has one argument, the array of rectangles rects
. pick
has no arguments. Arguments are always wrapped with a list, even if there aren’t any.
解题思路
这道题给出一个数组包括一组不重叠的矩形,要求我们每次从中间所有可选的点中间随机选择一个点出来。随机的部分我们可以利用 <cstdlib>
中的 rand()
来实现;另外我们还要考虑的点如下:
- 针对每一个矩形,可选的点是所有坐标为整数的点,并且四条边覆盖点也在可选择范围内。这意味着针对矩形
[0, 0, 1, 1]
我们实际上可选的点有四个:[0, 0], [0, 1], [1, 0], [1, 1]
。这一点在后续选择点坐标系要尤其注意选择的范围是 边长+1,并且计算面积时不能简单地用长 × 宽来代替,而是 (长 + 1)× (宽 + 1),代表可选的点的个数。 - 针对所有覆盖面积随机取点,因为矩形的面积不一定相同,所以均匀地从矩形数组中选矩形会导致出现问题。选取矩形的概率应该和其面积成正相关,我们可以利用转盘的思想将所有矩形的面积计算出来,然后在总面积范围内随机选取一个值,看那个值落在哪个矩形上。为了提高搜索速度可以直接使用 STL 中的
lower_bound()
使用二分查找进行搜索
代码部分我参考了:花花酱 LeetCode 882. Random Point in Non-overlapping Rectangles,大致如下:
#include <vector>
#include <cstdlib>
#include <algorithm>
class Solution {
public:
Solution(std::vector<std::vector<int>>& rects) {
m_rects = rects;
m_sum_areas = std::vector<int>(m_rects.size());
for (int i = 0; i < m_rects.size(); i++) {
// this area represents available points in that rectangle
m_sum_areas[i] = (m_rects[i][2] - m_rects[i][0] + 1) * (m_rects[i][3] - m_rects[i][1] + 1);
if (i > 0) {
m_sum_areas[i] += m_sum_areas[i - 1];
}
}
}
std::vector<int> pick() {
int index = std::lower_bound(m_sum_areas.begin(), m_sum_areas.end(), randInt(m_sum_areas.back()) + 1) -\
m_sum_areas.begin();
const std::vector<int>& chosen_rect = m_rects[index];
return { chosen_rect[0] + randInt(chosen_rect[2] - chosen_rect[0] + 1),\
chosen_rect[1] + randInt(chosen_rect[3] - chosen_rect[1] + 1)};
}
private:
std::vector<std::vector<int>> m_rects;
std::vector<int> m_sum_areas;
// return an integer between [0, n)
int randInt(int n) {
return rand() / static_cast<double>(RAND_MAX) * n;
}
};
- 时间复杂度:Solution: O(n), Pick: O(logn)
- 空间复杂度:O(n)