题目
给定一个非重叠轴对齐矩形的列表 rects,写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示:
整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。...示例 1:
输入:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
输出:
[null,[4,1],[4,1],[3,3]]...示例 2:
输入:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[...商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
类似题目:
LeetCode 528....按权重随机选择(前缀和+二分查找)
按照总的点的个数均匀分配
计算每个矩形的点的个数,以及点个数的前缀和
二分查找查找随机到的点所在的矩形,在该矩形内找到点的偏移位置
class Solution {