Участник:Lenaermakova/Random Point in Non-overlapping Rectangles

Материал из DISCOPAL
Перейти к: навигация, поиск

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

class Solution(object):
 
    def __init__(self, rects: List[List[int]]):
        self.s = []
        cumul = 0
        for rect in rects:
            x,y = rect[2] - rect[0] + 1, rect[3] - rect[1] + 1
            cumul += x * y
            self.s.append(cumul)
        self.rects = rects
 
    def pick(self) -> List[int]:
        r = random.randint(0, self.s[-1])
        left, right = 0, len(self.s) - 1
        while left < right:
            center = (right + left)//2
            if self.s[center] >= r:
                right = center
            else:
                left = center + 1
 
        x = self.rects[left][0] + random.randint(0,self.rects[left][2] - self.rects[left][0])
        y = self.rects[left][1] + random.randint(0,self.rects[left][3] - self.rects[left][1])
        return [x,y]