重庆建设工程造价信息总站,wordpress 主题地址,wordpress简体中文,南宁企业网站建设文章目录1. 题目2. 解题1. 题目
给定一个非重叠轴对齐矩形的列表 rects#xff0c;写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示#xff1a;
整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第 i 个矩形 rects [i] [x1#xff0…
文章目录1. 题目2. 解题1. 题目
给定一个非重叠轴对齐矩形的列表 rects写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示
整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第 i 个矩形 rects [i] [x1y1x2y2]其中 [x1y1] 是左下角的整数坐标[x2y2] 是右上角的整数坐标。
每个矩形的长度和宽度不超过 2000。
1 rects.length 100
pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
pick 最多被调用10000次。示例 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]]],[],[],[],[],[]]
输出:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]来源力扣LeetCode 链接https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 528. 按权重随机选择前缀和二分查找
按照总的点的个数均匀分配计算每个矩形的点的个数以及点个数的前缀和二分查找查找随机到的点所在的矩形在该矩形内找到点的偏移位置
class Solution {int n; //矩形个数int total;//总的点的个数int pointId;//选取的点的idvectorint presum;//所有矩形点的个数的前缀和vectorvectorint rectsize;//矩形的高宽vectorvectorint rects;//矩形
public:Solution(vectorvectorint rects) {n rects.size();presum.resize(n);rectsize.resize(n);this-rects rects;int r, c;for(int i 0; i n; i){r rects[i][3]-rects[i][1]1;//高c rects[i][2]-rects[i][0]1;//宽rectsize[i] {r, c};presum[i] r*c(i0 ? presum[i-1] : 0);//点个数的前缀和}total presum.back();}vectorint pick() {pointId rand()%total 1;//随机点int L 0, R n-1, mid, rectID;// 二分查找 presum 找到第一个 presum pointId 的矩形的IDwhile(L R){mid L((R-L)1);if(presum[mid] pointId)L mid1;else{if(mid0 || presum[mid-1] pointId){rectID mid;//找到该点所在的矩形IDbreak;}elseR mid-1;}}// idx 是该点在矩形内的idint idx pointId - (rectID 0 ? presum[rectID-1] : 0) - 1; // 读取 矩形的 高 宽int r rectsize[rectID][0], c rectsize[rectID][1];// 计算 相对左下角的偏移量int x idx%c, y idx/c;return {rects[rectID][0]x, rects[rectID][1]y};}
};84 ms 63.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
