[2022-06-09]914. 非重叠矩形中的随机点👋水塘抽样👋数学👋二分查找👋有序集合👋前缀和👋随机化

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles

难度: Medium
标签: 水塘抽样 数学 二分查找 有序集合 前缀和 随机化

[dreamjean]

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

Description

Difficulty: 中等

Related Topics: 水塘抽样, 数学, 二分查找, 有序集合, 前缀和, 随机化

给定一个由非重叠的轴对齐矩形的数组 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<sup>9</sup> <= a<sub>i</sub> < x<sub>i</sub> <= 10<sup>9</sup>
• -10<sup>9</sup> <= b<sub>i</sub> < y<sub>i</sub> <= 10<sup>9</sup>
• x<sub>i</sub> - a<sub>i</sub> <= 2000
• y<sub>i</sub> - b<sub>i</sub> <= 2000
• 所有的矩形不重叠。
• pick` 最多被调用 10⁴ 次。

Solution

思路

• 矩形覆盖的点有 m * n 个, 利用前缀和数组存储前 i 个矩阵所对应的整数坐标点个数
• 使用随机函数和总坐标数 sum 生成一个数 k， 利用 k 找出在前 i 个矩阵所对应中的那一个
• 使用二分查找的方法进行查找 k 所在的矩阵, 然后在该矩阵中使用随机数随机生成 x 和 y

Language: JavaScript

/**
 * @param {number[][]} rects
 */
var Solution = function(rects) {
    this.rects = rects;
    this.arr = [];
    this.sum = 0;
    rects.forEach(([x1, y1, x2, y2]) => { 
        const m = x2 - x1 + 1 
        const n = y2 - y1 + 1
        this.sum += m * n
        this.arr.push(this.sum)
    })
};

/**
 * @return {number[]}
 */
Solution.prototype.pick = function() {
    let k = Math.random() * this.sum;
    let [left, right] = [0, this.arr.length - 1]
    while (left < right) {
        const mid = (left + right) >>> 1;
        this.arr[mid] >= k ? (right = mid) : (left = mid + 1);
    }

    const [x1, y1, x2, y2] = this.rects[right];
    const da = ~~(Math.random() * (x2 - x1 + 1));
    const db = ~~(Math.random() * (y2 - y1 + 1));
    return [x1 + da, y1 + db];
};


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