leetcode：497. Random points in non overlapping rectangles [random + prefix and bisection + passing]

analysis

First, record the number of points in each rectangle
Then make prefix and
When querying, generate a 1 Random number to all points
According to prefix and bisection, decide which rectangle to divide into
And then in this rectangle random Two coordinates are enough

ac code

class Solution:

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

        self.tot = self.preSum[-1]



    def pick(self) -> List[int]:
        r = random.randint(1, self.tot)
        idx = bisect_left(self.preSum, r)
        a, b, x, y = self.rects[idx]
        return self.helper(a, b, x, y)


    
    def helper(self, a, b, x, y):
        rx = random.randint(a, x)
        ry = random.randint(b, y)
        return [rx, ry]



# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()

summary

Random by chance