返回

[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,大致如下:

#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)
Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy