LeetCode：497. Random points in non overlapping rectangles -- medium

subject

497. Random points in non overlapping rectangles
Given an array of rectangles aligned by non overlapping axes rects , among rects[i] = [ai, bi, xi, yi] Express (ai, bi) It's No i Bottom left corner of rectangle ,(xi, yi) It's No i The upper right corner of a rectangle . Design an algorithm to randomly select an integer point covered by a rectangle . Points on the perimeter of a rectangle are also considered to be covered by the rectangle . All points that meet the requirements must be returned with equal probability .

Any integer point in the space covered by a given rectangle can be returned .

Please note that , An integer point is a point with integer coordinates .

Realization Solution class :

• Solution(int[][] rects) With the given rectangular array rects Initialize object .
• int[] pick() Returns a random integer point [u, v] In the space covered by a given rectangle .

Example 1：

Input :
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
Output :
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

explain ：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]

Tips ：

• 1 <= rects.length <= 100
• rects[i].length == 4
• -109 <= ai < xi <= 109
• -109 <= bi < yi <= 109
• xi - ai <= 2000
• yi - bi <= 2000
• All rectangles do not overlap .
• pick At most called 104 Time .

Their thinking

• The small left corner of a given rectangle （a,b）, Upper right corner （x,y）, Then the number of points in the rectangle is （x-a+1）*（y-b+1）
• We can choose a random number from all the points , From the sum of the number prefixes, it is determined in which matrix .
• Then from the width or height of the matrix , Determine the number of random points in the row .

Code

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

    def pick(self) -> List[int]:
        k = randrange(self.sum[-1])
        rectIndex = bisect_right(self.sum, k) - 1
        a, b, _, y = self.rects[rectIndex]
        da, db = divmod(k - self.sum[rectIndex], y - b + 1)
        return [a + da, b + db]

Running results