【497. 非重叠矩形中的随机点】

  • Post author:
  • Post category:其他


来源:

力扣(LeetCode)


描述:

给定一个由非重叠的轴对齐矩形的数组

rects

,其中

rects[i] = [ai, bi, xi, yi]

表示

(ai, bi)

是第

i

个矩形的左下角点,

(xi, yi)

是第

i

个矩形的右上角角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在一个给定的矩形覆盖的空间内任何整数点都有可能被返回。


请注意

,整数点是具有整数坐标的点。

实现

Solution

类:


  • Solution(int[][] rects)

    用给定的矩形数组

    rects

    初始化对象。

  • int[] pick()

    返回一个随机的整数点

    [u, v]

    在给定的矩形所覆盖的空间内。


示例 1:

输入: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]

解释:
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]


提示:


  • 1 <= rects.length <= 100

  • rects[i].length == 4
  • -10

    9

    <= ai < xi <= 10

    9
  • -10

    9

    <= bi < yi <= 10

    9

  • xi - ai <= 2000

  • yi - bi <= 2000
  • 所有的矩形不重叠。

  • pick

    最多被调用 10

    4

    次。


方法:前缀和 + 二分查找


思路

在这里插入图片描述


代码:

class Solution {
public:
    Solution(vector<vector<int>>& rects) : rects{rects} {
        this->arr.emplace_back(0);
        for (auto & rect : rects) {
            this->arr.emplace_back(arr.back() + (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1));
        }
    }
    
    vector<int> pick() {
        uniform_int_distribution<int> dis(0, arr.back() - 1);
        int k = dis(gen) % arr.back();
        int rectIndex = upper_bound(arr.begin(), arr.end(), k) - arr.begin() - 1;
        k = k - arr[rectIndex];
        int a = rects[rectIndex][0], b = rects[rectIndex][1];
        int y = rects[rectIndex][3];
        int col = y - b + 1;
        int da = k / col;
        int db = k - col * da;
        return {a + da, b + db};
    }    
private:
    vector<int> arr;
    vector<vector<int>>& rects;
    mt19937 gen{random_device{}()};
};

执行用时:84 ms, 在所有 C++ 提交中击败了40.07%的用户

内存消耗:65.6 MB,在所有 C++ 提交中击败了65.70%的用户

复杂度分析

时间复杂度:构造函数复杂度为 O(n),pick 函数复杂度为 O(logn),其中 n 为 rects 的长度。构造函数需要构造前缀和数组,pick 函数需要在前缀和数组内进行二分。

空间复杂度:构造函数复杂度为O(n),pick 函数复杂度为 O(1),其中 n 为rects 的长度。构造函数需要构造前缀和数组,pick 函数只需要使用常数空间。



版权声明:本文为Sugar_wolf原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。