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

题目描述

给定一个由非重叠的轴对齐矩形的数组 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 个矩形，此矩形的面积为 $A_i$，$[0,…,i]$ 所有矩形的面积和为 $S_i$，若选择该矩形的概率为 $\frac{A_i}{S_i}$，那么最终每个矩形被选中的概率为 $\frac{A}{S_n}$，其中 $A$ 为被选中矩形的面积，$S_n$ 为所有矩形面积和。
证：不失一般性，假设最终选择第 $k$ 个矩形，此矩形的面积为 $A_k$，则有：

$\begin{aligned} P (最终选择 k) & = P (选中第 k 个矩形) \times P (不选第 k + 1 个) \times . . . \times P (不选第 n 个) \\ = \frac{A_{k}}{S_{k}} \times (1 - \frac{A_{k + 1}}{S_{k} + A_{k + 1}}) \times . . . \times (1 - \frac{A_{n}}{S_{n}}) \\ = \frac{A_{k}}{S_{k}} \times \frac{S_{k}}{S_{k + 1}} \times . . . \times \frac{S_{n - 1}}{S_{n}} \\ = \frac{A_{k}}{S_{n}} \end{aligned}$

代码

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$，而不是首个矩形的面积。

代码

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};
    }
};