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

### 题目描述

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.`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 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.

### 解题思路

• 针对每一个矩形，可选的点是所有坐标为整数的点，并且四条边覆盖点也在可选择范围内。这意味着针对矩形 `[0, 0, 1, 1]` 我们实际上可选的点有四个：`[0, 0], [0, 1], [1, 0], [1, 1]`。这一点在后续选择点坐标系要尤其注意选择的范围是 边长+1，并且计算面积时不能简单地用长 × 宽来代替，而是 （长 + 1）× （宽 + 1），代表可选的点的个数。
• 针对所有覆盖面积随机取点，因为矩形的面积不一定相同，所以均匀地从矩形数组中选矩形会导致出现问题。选取矩形的概率应该和其面积成正相关，我们可以利用转盘的思想将所有矩形的面积计算出来，然后在总面积范围内随机选取一个值，看那个值落在哪个矩形上。为了提高搜索速度可以直接使用 STL 中的 `lower_bound()` 使用二分查找进行搜索

``````#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)