LeetCode 497. 非重叠矩形中的随机点(前缀和+二分)

---

题目

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

解法：前缀和+二分

整体思路：先随机确定在哪个矩形内取点，再在该矩形内随机取点。

对于第二步，根据矩形特质，只需在该矩形的 XY 坐标范围内随机即可确保等概率

对于第一步（随机确定矩形）为了确保是等概率，需要结合每个矩形覆盖的点数来做。

矩形 $\text{rects}[i]$ 的左下角点为 $(a_i,b_i)$, 右上角点为 $(x_i,y_i)$，则它覆盖的整数点有 $s_i=(x_i-a_i+1)\times (y_i-b_i+1)$个。

将 $\text{rects}[0]$ 覆盖的点编号为 1 至 $s_0$，$\text{rects}[1]$ 覆盖的整数点有 $s_1$个，编号为 $s_0+1$ 至 $s_0+s_1$，依此类推。

预处理一个前缀和数组 arr（前缀和数组下标默认从 1 开始），其中 arr[i] 代表前 i 个矩形的覆盖的点数之和（即下标范围 [0, i - 1] 的点数总和），最终 arr[n] 为所有矩形的覆盖的总点数，可以在 [1, arr[n]] 范围内随机，假定随机到的值为 k，然后利用 arr 数组的具有单调性，进行「二分」，找到 k 所在的矩形，然后在该矩形中进行随机，得到最终的随机点。

class Solution {
    
    Random rand;
    int[][] rects;
    // arr[0] = 0;
    // arr[1] = n; 第一个矩形有n个点
    // arr[2] = m + n; 第二个矩形有m个点
    List<Integer> arr; // 前缀和数组
    int num;      // 一共有 num - 1 个矩形
    public Solution(int[][] rects) {
    
        rand = new Random();
        this.rects = rects;
        arr = new ArrayList<>();
        arr.add(0);
        // 构造前缀和数组
        for (int[] r : rects) {
    
            int a = r[0], b = r[1], x = r[2], y = r[3];
            // 前面矩形覆盖的总点数
            int n = arr.get(arr.size() - 1);
            // 当前矩形覆盖的点数
            int m = (x - a + 1) * (y - b + 1);
            arr.add(n + m);
        }
        num = arr.size();
    }
    
    public int[] pick() {
    
        // 1. 确定在哪个矩形内取点
        // 获取[0, rects覆盖的总点数 - 1]之间的一个随机数
        int k = rand.nextInt(arr.get(num - 1));
        // 利用二分确定该点属于第几个矩形（对应到rects的索引应该减1）
        // k + 1 是因为点的编号是从1开始的
        int rectIndex = binarySearch(arr, k + 1);
        // 2. 在rects[rectIndex - 1]对应的矩形内选点
        int[] rect = rects[rectIndex - 1];
        int x = rect[2] - rect[0] + 1;
        int y = rect[3] - rect[1] + 1;
        int a = rand.nextInt(x) + rect[0];
        int b = rand.nextInt(y) + rect[1];
        return new int[]{
    a, b};
    }

    private int binarySearch(List<Integer> arr, int target) {
    
        int left = 0, right = num;
        while (left < right) {
    
            int mid = left + (right - left) / 2;
            if (arr.get(mid) < target) {
    
                left = mid + 1;
            } else {
    
                right = mid;
            }
        }
        return left;
    }
}

/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(rects); * int[] param_1 = obj.pick(); */

• 时间复杂度：构造函数复杂度为 $O(n)$，$\text{pick}$ 函数复杂度为 $O(\log n)$，其中 $n$ 为 $\text{rects}$ 的长度。构造函数需要构造前缀和数组，$\text{pick}$函数需要在前缀和数组内进行二分。

• 空间复杂度：构造函数复杂度为 $O(n)$，$\text{pick}$ 函数复杂度为 $O(1)$。构造函数需要构造前缀和数组，$\text{pick}$ 函数只需要使用常数空间。

Reference

• 非重叠矩形中的随机点