0%

[Leetcode]497. Random Point in Non-overlapping Rectangles (C++)

题目描述

题目链接:497. Random Point in Non-overlapping Rectangles

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick 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.ith 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 exceed 2000.
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 most 10000 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,大致如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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)