中等

问题描述

给定一个由非重叠的轴对齐矩形的数组 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
• -109 <= ai < xi <= 109
• -109 <= bi < yi <= 109
• xi - ai <= 2000
• yi - bi <= 2000
• 所有的矩形不重叠。
• pick 最多被调用 104 次。

前缀和 + 二分查找

矩形 $rects[i]$ 的左下角点 $(a_i, b_i)$，右上角点 $(x_i, y_i)$，覆盖的点共有 $(x_i - a_i + 1) \times (y_i - b_i + 1)$ 个，要从被 $n$ 个矩形覆盖的区域中抽取坐标，首先对每个矩形的面积进行累加生成一个前缀和数组，然后从累加的范围内随机抽取一个数，因为对矩形面积进行了累加，这样抽取使得抽取到的数落在每个矩形上的概率是相等的，由于矩形面积生成的前缀和数组具有单调性，可以使用二分查找确定是哪个矩形，然后在从矩形的坐标范围内生成点数。

/**
 * @param {number[][]} rects
 */
var Solution = function (rects) {
  this.n = rects.length
  this.rects = rects
  this.list = []
  for (const [a, b, x, y] of rects) {
    const w = x - a + 1
    const h = y - b + 1
    this.list.push(w * h + (this.list[this.list.length - 1] || 0))
  }
}

/**
 * @return {number[]}
 */
Solution.prototype.pick = function () {
  const n = ~~(Math.random() * (this.list[this.n - 1] + 1))
  let l = 0
  let r = this.n - 1
  while (l < r) {
    const m = ((r - l) >> 1) + l
    if (this.list[m] < n) {
      l = m + 1
    } else {
      r = m
    }
  }
  const [a, b, x, y] = this.rects[r]
  const u = ~~(Math.random() * (x - a + 1)) + a
  const v = ~~(Math.random() * (y - b + 1)) + b
  return [u, v]
}

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

• 时间复杂度：构造函数复杂度为 $O(n)$，$\text {pick}$ 函数复杂度为 $O(log\;n)$
• 空间复杂度：构造函数复杂度为 $O(n)$，$\text {pick}$ 函数复杂度为 $O(1)$