497. Random Point in Non-overlapping Rectangles

[Tcdian]

497. Random Point in Non-overlapping Rectangles

给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

提示：

1. 整数点是具有整数坐标的点。
2. 矩形周边上的点包含在矩形覆盖的空间中。
3. 第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
4. 每个矩形的长度和宽度不超过 2000。
5. 1 <= rects.length <= 100
6. pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
7. pick 最多被调用10000次。

Example 1

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2

Input: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax

输入是两个列表：调用的子例程及其参数。Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[][]} rects
 */
var Solution = function(rects) {
    this.rects = rects;
    this.prefixSum = new Array(rects.length);
    this.points = 0;
    for (let i = 0; i < rects.length; i++) {
        this.prefixSum[i] = this.points;
        const [x1, y1, x2, y2] = rects[i];
        for (let x = x1; x <= x2; x++) {
            for (let y = y1; y <= y2; y++) {
                this.points += 1;
            }
        }
    }
};

/**
 * @return {number[]}
 */
Solution.prototype.pick = function() {
    let random = Math.floor(Math.random() * this.points) + 1;
    let ractIndex = this.rects.length - 1;
    while (this.prefixSum[ractIndex] >= random) {
        ractIndex -= 1;
    }
    random -= this.prefixSum[ractIndex];
    const [x1, y1, x2, y2] = this.rects[ractIndex];
    for (let x = x1; x <= x2; x++) {
        for (let y = y1; y <= y2; y++) {
            if (--random === 0) {
                return [x, y];
            }
        }
    }
    return [-1, -1];
};

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

• TypeScript Solution

class Solution {
    private prefixSum: number[];
    private points: number;
    constructor(private rects: number[][]) {
        this.prefixSum = new Array(rects.length);
        this.points = 0;
        for (let i = 0; i < rects.length; i++) {
            this.prefixSum[i] = this.points;
            const [x1, y1, x2, y2] = rects[i];
            for (let x = x1; x <= x2; x++) {
                for (let y = y1; y <= y2; y++) {
                    this.points += 1;
                }
            }
        }
    }

    pick(): number[] {
        let random = Math.floor(Math.random() * this.points) + 1;
        let ractIndex = this.rects.length - 1;
        while (this.prefixSum[ractIndex] >= random) {
            ractIndex -= 1;
        }
        random -= this.prefixSum[ractIndex];
        const [x1, y1, x2, y2] = this.rects[ractIndex];
        for (let x = x1; x <= x2; x++) {
            for (let y = y1; y <= y2; y++) {
                if (--random === 0) {
                    return [x, y];
                }
            }
        }
        return [-1, -1];
    }
}

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