leetcode 497. 非重叠矩形中的随机点 random point in non overlapping rectangles - python

目录

https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles/

这道题目很独特，要求返回随机的答案，应该是通过检查答案分布情况来判断是否通过。

因为前提是所有矩形不重合。所以可以分为两步做，第一步是随机选择矩形，第二步则是在矩形上随机选点。

难点在于如何高效的随机选择矩形。可以计算每个矩形的点数，然后做一个累加的数组，数组第一位是第一个矩形的点数，第 n 位是前 n 个矩形的点数和。

然后从 0 到面积和取随机数，看落到那个矩形上，就选哪个矩形。可以使用二分搜索提高效率。

import bisect
class Solution:

    def __init__(self, rects: List[List[int]]):
        self.r = rects
        self.p = []
        cur = 0
        for r in rects:
            cur += (abs(r[2] - r[0])+1) * (abs(r[3] - r[1])+1)
            self.p.append(cur)

    def pick(self) -> List[int]:
        c = random.randint(0, self.p[-1]-1)
        i = bisect.bisect(self.p, c)
        x = random.randint(self.r[i][0], self.r[i][2])
        y = random.randint(self.r[i][1], self.r[i][3])
        return [x, y]