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

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀面积和 + 二分查找

1. 📝 题目描述

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

2. 🎯 s.1 - 前缀面积和 + 二分查找

c

typedef struct {
    int** rects;
    int rectsSize;
    int* prefix;
    int total;
} Solution;

Solution* solutionCreate(int** rects, int rectsSize, int* rectsColSize) {
    Solution* obj = (Solution*)malloc(sizeof(Solution));
    obj->rects = rects;
    obj->rectsSize = rectsSize;
    obj->prefix = (int*)malloc(sizeof(int) * rectsSize);
    int sum = 0;
    for (int i = 0; i < rectsSize; i++) {
        sum += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
        obj->prefix[i] = sum;
    }
    obj->total = sum;
    return obj;
}

int* solutionPick(Solution* obj, int* retSize) {
    *retSize = 2;
    int* res = (int*)malloc(sizeof(int) * 2);
    int target = rand() % obj->total + 1;
    int lo = 0, hi = obj->rectsSize - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (obj->prefix[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    int* r = obj->rects[lo];
    int w = r[2] - r[0] + 1;
    int offset = target - (lo > 0 ? obj->prefix[lo - 1] : 0) - 1;
    res[0] = r[0] + offset % w;
    res[1] = r[1] + offset / w;
    return res;
}

void solutionFree(Solution* obj) {
    free(obj->prefix);
    free(obj);
}

js

/**
 * @param {number[][]} rects
 */
var Solution = function (rects) {
  this.rects = rects
  this.prefix = []
  let sum = 0
  for (const [a, b, x, y] of rects) {
    sum += (x - a + 1) * (y - b + 1)
    this.prefix.push(sum)
  }
  this.total = sum
}

/**
 * @return {number[]}
 */
Solution.prototype.pick = function () {
  const target = Math.floor(Math.random() * this.total) + 1
  let lo = 0,
    hi = this.prefix.length - 1
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (this.prefix[mid] < target) lo = mid + 1
    else hi = mid
  }
  const [a, b, x, y] = this.rects[lo]
  const w = x - a + 1
  const offset = target - (lo > 0 ? this.prefix[lo - 1] : 0) - 1
  return [a + (offset % w), b + Math.floor(offset / w)]
}

py

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.prefix = []
        total = 0
        for a, b, x, y in rects:
            total += (x - a + 1) * (y - b + 1)
            self.prefix.append(total)
        self.total = total

    def pick(self) -> List[int]:
        target = random.randint(1, self.total)
        lo, hi = 0, len(self.prefix) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self.prefix[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        a, b, x, y = self.rects[lo]
        w = x - a + 1
        offset = target - (self.prefix[lo - 1] if lo > 0 else 0) - 1
        return [a + offset % w, b + offset // w]

• 时间复杂度：初始化 $O(k)$，每次 pick $O(\log k)$，其中 $k$ 是矩形数量
• 空间复杂度：$O(k)$

算法思路：

• 按每个矩形包含的整数点数构建前缀和
• 随机一个 $[1,total]$ 的数，二分定位到对应矩形
• 在矩形内通过偏移量计算具体坐标