LeetCode497. 非重叠矩形中的随机点

题目描述

本题目来自LeetCode上的『497. 非重叠矩形中的随机点』

给定一个由非重叠的轴对齐矩形的数组 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], [2, 2, 4, 6]]], [], [], [], [], []]
输出:
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

解释：
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 <= 2000yi - bi <= 2000
• 所有的矩形不重叠。
• pick最多被调用 10^4 次。

题解1 - 水塘抽样

基本思路就是以面积为权重选择矩形（几何概型），然后再在被选中的矩形中随机选点。
从前向后遍历矩形，设当前遍历到第 i 个矩形，此矩形的面积为 Ai，[0,…,i] 所有矩形的面积和为 Si，若选择该矩形的概率为 AiSi，那么最终每个矩形被选中的概率为 ASn，其中 A 为被选中矩形的面积，Sn 为所有矩形面积和。
证： 不失一般性，假设最终选择第 k 个矩形，此矩形的面积为 Ak，则有：

P(最终选择k)=P(选中第k个矩形)×P(不选第k+1个)×...×P(不选第n个)=AkSk×(1−Ak+1Sk+Ak+1)×...×(1−AnSn)=AkSk×SkSk+1×...×Sn−1Sn=AkSn

代码

cpp

class Solution {
private:
int n;
    vector<vector<int>>& rects;
    mt19937 gen{random_device{}()};
public:
    Solution(vector<vector<int>>& _rects) : rects(_rects) {
        n = rects.size();
    }
    
    vector<int> pick() {
        int idx = -1, sum = 0;
        
        for (int i = 0; i < n; ++i) {
            int a = rects[i][0], b = rects[i][1];
            int x = rects[i][2], y = rects[i][3];
            int area = (x - a + 1) * (y - b + 1);
            sum += area;
            uniform_int_distribution<int> dis(0, sum - 1);
            if (dis(gen) < area) {
                idx = i;
            }
        }
        int a = rects[idx][0], b = rects[idx][1];
        int x = rects[idx][2], y = rects[idx][3];
        uniform_int_distribution<int> dis1(0, x - a);
        uniform_int_distribution<int> dis2(0, y - b);
        return {dis1(gen) + a, dis2(gen) + b};
    }
};

复杂度分析

• 时间复杂度：每次 pick() 操作为 O(n)
• 空间复杂度：O(1)

题解2 - 前缀和+二分

设所有矩形一共有 total 个点，在这 total 个点中随机取一个点就是所要求的答案，但直接这么模拟会 TLE。考虑优化，先选出在哪个矩形中，再在矩形中选点。使用前缀和来保存矩形的点的数目，在 total 个点中随机取一个点，通过查找前缀数组来确定在哪个矩形中，由于前缀数组满足单调性，查找可以使用二分查找。
注： 随机取值的范围为 [0,total]，因此前缀数组的首个值为 0，而不是首个矩形的面积。

代码

cpp

class Solution {
private:
    vector<int> sum;
    vector<vector<int>>& rects;
    mt19937 gen{random_device{}()};
public:
    Solution(vector<vector<int>>& _rects) : rects(_rects) {
        sum.emplace_back(0);
        for (const auto& rect : rects) {
            sum.emplace_back(sum.back() + (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1));
        }
    }
    
    vector<int> pick() {
        uniform_int_distribution<int> dis(0, sum.back() - 1);
        int r = dis(gen);
        int idx = upper_bound(sum.begin(), sum.end(), r) - sum.begin() - 1;
        int a = rects[idx][0], b = rects[idx][1];
        int x = rects[idx][2], y = rects[idx][3];
        uniform_int_distribution<int> dis1(0, x - a);
        uniform_int_distribution<int> dis2(0, y - b);
        return {dis1(gen) + a, dis2(gen) + b};
    }
};

复杂度分析

• 时间复杂度：构造函数为 O(n)，每次 pick() 操作为 O(logn)
• 空间复杂度：O(n)