Medium

题目描述

给你一个由非重叠的轴对齐矩形的数组 rects，其中 rects[i] = [ai, bi, xi, yi] 表示第 i 个矩形的左下角是 (ai, bi)，右上角是 (xi, yi)。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周边上的点也算是被矩形覆盖。

矩形覆盖的空间内的任何整数点都应该等概率地被返回。

注意：整数点是坐标为整数的点。

实现 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
  • -109 <= ai < xi <= 109
  • -109 <= bi < yi <= 109
  • xi - ai <= 2000
  • yi - bi <= 2000
  • 所有的矩形互不重叠。
  • 最多会调用 pick 方法 104 次。

解题思路

这道题要求在多个非重叠矩形中等概率地选择一个整数点。关键思路是按矩形面积进行加权随机选择。

主要思路：

  1. 计算每个矩形的面积：对于矩形 [a, b, x, y]，其包含的整数点个数为 (x - a + 1) * (y - b + 1)

  2. 构建前缀和数组：用于支持按面积加权的随机选择。面积越大的矩形被选中的概率越高

  3. 两步随机过程：

    • 第一步：根据面积权重随机选择一个矩形（使用二分查找）
    • 第二步：在选中的矩形内随机选择一个整数点

具体实现：

  • 初始化时计算所有矩形的面积并构建前缀和数组
  • pick() 时先生成 [1, total_area] 范围内的随机数，用二分查找确定对应的矩形
  • 然后在该矩形内随机生成坐标点

这种方法保证了每个整数点被选中的概率相等，时间复杂度为 O(log n)，空间复杂度为 O(n)。

代码实现

class Solution {
private:
    vector<vector<int>> rects;
    vector<int> prefixSum;
    
public:
    Solution(vector<vector<int>>& rects) : rects(rects) {
        prefixSum.push_back(0);
        for (auto& rect : rects) {
            int area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            prefixSum.push_back(prefixSum.back() + area);
        }
    }
    
    vector<int> pick() {
        int total = prefixSum.back();
        int target = rand() % total + 1;
        
        int idx = lower_bound(prefixSum.begin() + 1, prefixSum.end(), target) - prefixSum.begin();
        if (prefixSum[idx] < target) idx++;
        idx--;
        
        auto& rect = rects[idx];
        int x = rand() % (rect[2] - rect[0] + 1) + rect[0];
        int y = rand() % (rect[3] - rect[1] + 1) + rect[1];
        
        return {x, y};
    }
};

class Solution:

    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.prefix_sum = [0]
        for rect in rects:
            area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)
            self.prefix_sum.append(self.prefix_sum[-1] + area)

    def pick(self) -> List[int]:
        target = random.randint(1, self.prefix_sum[-1])
        
        left, right = 0, len(self.rects) - 1
        while left < right:
            mid = (left + right) // 2
            if self.prefix_sum[mid + 1] < target:
                left = mid + 1
            else:
                right = mid
        
        rect = self.rects[left]
        x = random.randint(rect[0], rect[2])
        y = random.randint(rect[1], rect[3])
        
        return [x, y]

public class Solution {
    private int[][] rects;
    private int[] prefixSum;
    private Random rand;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.rand = new Random();
        prefixSum = new int[rects.Length + 1];
        
        for (int i = 0; i < rects.Length; i++) {
            int area = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
            prefixSum[i + 1] = prefixSum[i] + area;
        }
    }
    
    public int[] Pick() {
        int target = rand.Next(1, prefixSum[prefixSum.Length - 1] + 1);
        
        int left = 0, right = rects.Length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid + 1] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        int[] rect = rects[left];
        int x = rand.Next(rect[0], rect[2] + 1);
        int y = rand.Next(rect[1], rect[3] + 1);
        
        return new int[] {x, y};
    }
}

var Solution = function(rects) {
    this.rects = rects;
    this.prefixSum = [0];
    
    for (let rect of rects) {
        let area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
        this.prefixSum.push(this.prefixSum[this.prefixSum.length - 1] + area);
    }
};

Solution.prototype.pick = function() {
    let target = Math.floor(Math.random() * this.prefixSum[this.prefixSum.length - 1]) + 1;
    
    let left = 0, right = this.rects.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (this.prefixSum[mid + 1] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    let rect = this.rects[left];
    let x = Math.floor(Math.random() * (rect[2] - rect[0] + 1)) + rect[0];
    let y = Math.floor(Math.random() * (rect[3] - rect[1] + 1)) + rect[1];
    
    return [x, y];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(n)O(n)
pick()O(log n)O(1)

其中 n 是矩形的数量。初始化时需要计算所有矩形面积并构建前缀和数组，pick() 操作通过二分查找选择矩形，然后在常数时间内生成随机点。

相关题目