题目地址: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/description/
题目描述：
Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.
Note:
1、 Anintegerpointisapointthathasintegercoordinates.；
2、 Apointontheperimeterofarectangleisincludedinthespacecoveredbytherectangles.；
3、 ithrectangle=rects[i]=[x1,y1,x2,y2],where[x1,y1]aretheintegercoordinatesofthebottom-leftcorner,and[x2,y2]aretheintegercoordinatesofthetop-rightcorner.；
4、 lengthandwidthofeachrectangledoesnotexceed2000.；
5、 1<=rects.length<=100；
6、 pickreturnapointasanarrayofintegercoordinates[p_x,p_y]；
7、 pickiscalledatmost10000times.；
Example 1:
Input:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:
[null,[4,1],[4,1],[3,3]]
Example 2:
Input:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
Explanation of Input Syntax:
Theinput is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.
题目大意
给出了几个不重叠的长方形，按照覆盖面积随机在这些长方形中随机取横纵坐标都是整数的点。
解题方法
既然看到不重叠了，而且明显同一长方形内部的整数点被选择的概率相同，不同长方形内部的点被选择的概率等于该长方形的面积。那么我们肯定想到的是首先按照面积随机选择一个长方形，然后再在长方形中随机选择一个整数点就ok了。
所以，怎么按照面积选点呢？于是528. Random Pick with Weightopen in new window就派到用场了。思想是把PDF转换成CDF，然后再随机选择点，找到这个点的upper_bound。整体的思路还是挺新颖的，所以一定得先把528题做出来才能做这个题。
这个题的做法基本一致，我提交错误好几次，最后通过思考题目给出的测试用例找到了原因。看题目给的第二个测试用例中，有个长方形是[1, 0, 3, 0]，这个面积不是0么？但是题目也认为这个是有3个整数点的长方形。所以求面积的方式得改啊，这个题不是简单的求长方形的面积，而是求长方形中整数点的个数，计算方式是(x2 - x1 + 1) * (y2 - y1 + 1)。
初始化的时间复杂度是O(N)，每次查询的时间复杂度是O(logN)，空间复杂度是O(N)。
class Solution(object):
def __init__(self, rects):
"""
:type rects: List[List[int]]
"""
self.rects = rects
self.N = len(rects)
areas = [(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects]
self.preSum = [0] * self.N
self.preSum[0] = areas[0]
for i in range(1, self.N):
self.preSum[i] = self.preSum[i - 1] + areas[i]
self.total = self.preSum[-1]
def pickRect(self):
rand = random.randint(0, self.total - 1)
return bisect.bisect_right(self.preSum, rand)
def pickPoint(self, rect):
x1, y1, x2, y2 = rect
x = random.randint(x1, x2)
y = random.randint(y1, y2)
return x, y
def pick(self):
"""
:rtype: List[int]
"""
rectIndex = self.pickRect()
rect = self.rects[rectIndex]
return self.pickPoint(rect)
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
参考资料：
https://blog.csdn.net/fuxuemingzhu/article/details/81807215
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发