『LeetCode』497 非重叠矩形中的随机点

题目

给定一个由非重叠的轴对齐矩形的数组 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} <= a^{i} < x^{i} <= 10^{9}\)
\(-10^{9} <= b^{i} < y^{i} <= 10^{9}\)
\(x^{i} - a^{i} <= 2000\)
\(y^{i} - b^{i} <= 2000\)
所有的矩形不重叠。
pick 最多被调用 \(10^{4}\) 次。

相似题目

题解

【非重叠矩形中的随机点】按权重随机采样

随机采样

由于矩形不重叠，所以可以将随机点选取步骤分为两步：

以矩形中整数点的个数为权重随机选一个矩形
在选中的矩形中随机选一个点

需要注意，矩形面积有可能等于 0 但面积为 0 的矩形边界上的点是可能取到的，所以应该计算矩阵中整数点的个数而非面积。

因为题目给出的矩形最多只有 100 个，是否使用二分效率差别不大

# Code language: Python
class Solution:

    def __init__(self, rects: List[List[int]]):
        s = [(y - b + 1) * (x - a + 1) for a, b, x, y in rects]
        self.rects = rects
        self.p = list(itertools.accumulate(s))
        self.right = self.p[-1]

    def pick(self) -> List[int]:
        r = random.randint(0, self.right)
        for idx in range(len(self.p)):
            if self.p[idx] > r:
                break
        a, b, x, y = self.rects[idx]
        return [random.randint(a, x), random.randint(b, y)]

# Code language: Python
class Solution:

    def __init__(self, rects: List[List[int]]):
        self.weight = [(y - b + 1) * (x - a + 1) for a, b, x, y in rects]
        self.rects = rects

    def pick(self) -> List[int]:
        a, b, x, y = random.choices(self.rects, weights=self.weight)[0]
        return [random.randint(a, x), random.randint(b, y)]

二分方法：

# Code language: Python
class Solution:

    def __init__(self, rects: List[List[int]]):
        s = [(y - b + 1) * (x - a + 1) for a, b, x, y in rects]
        self.rects = rects
        self.p = list(itertools.accumulate(s))
        self.right = self.p[-1]

    def pick(self) -> List[int]:
        r = random.randint(0, self.right)
        a, b, x, y = self.rects[bisect.bisect_left(self.p, r)]
        return [random.randint(a, x), random.randint(b, y)]

时间复杂度: \(O(n)\)
空间复杂度: \(O(n)\)

最后

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』497 非重叠矩形中的随机点

题目

标签

相似题目

题解

随机采样

最后