生也有涯，知也无涯。这篇文章主要讲述497. Random Point in Non-overlapping Rectangles相关的知识，希望能为你提供帮助。
1. 问题
给定一系列不重叠的矩形，在这些矩形中随机采样一个整数点。
2. 思路
【497. Random Point in Non-overlapping Rectangles】（1）一个矩形的可采样点个数就相当于它的面积，可以先依次对每个矩形的面积累加存起来（相当于概率分布中的分布累积函数CDF，Cumulative Distribution Function）。
（2）从 [1, 总面积] 中随机取一个数n（面积），表示要取第几个点，找到这个点即可完成题目要求的随机采样。
（3）找点可以先使用python的bisect_left方法，根据这个数（面积）在多个累加面积之间寻找合适的位置（第几个矩形）。然后根据这个数（面积）在那个矩形里找到这个点。
（4）bisect_left的作用是对已排序数组，查找目标数值将会插入的位置并返回（但是不会插入），数值相同时返回靠左的位置。
3. 代码
import random
import bisectclass Solution(object):
def __init__(self, rects):
"""
:type rects: List[List[int]]
"""
self.rects = rects
sums = 0
self.accumulate = []
for x1, y1, x2, y2 in rects:
sums += (y2 - y1 + 1) * (x2 - x1 + 1)
self.accumulate.append(sums)def pick(self):
"""
:rtype: List[int]
"""
n = random.randint(1, self.accumulate[-1])
i = bisect.bisect_left(self.accumulate, n)
x1, y1, x2, y2 = self.rects[i]
if(i >
0):
n -= self.accumulate[i - 1]
n -= 1
return [x1 + n % (x2 - x1 + 1), y1 + n / (x2 - x1 + 1)]# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()推荐阅读
- poj3321-Apple Tree（DFS序+树状数组）
- Error: Default interface methods are only supported starting with Android N (--min-api 24): java.io.
- 分享一下身边朋友自学android开发及找工作的那些事！不足勿喷
- 超实用教程，教你用墨刀做出小红书app原型
- WinXP内码输入法如何添加到Vista中
- WinXP如何按照笔划来排列文件名
- WinXP无法打开安全中心且提示不可用的处理办法
- WinXP无法重装IE怎样办？
- 如何处理WindowsXP无法安装显卡驱动提示不兼容问题