说在前面
🎈每天进行一道算法题目练习，今天的题目是“非重叠矩形中的随机点”。
问题描述
给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。
在一个给定的矩形覆盖的空间内任何整数点都有可能被返回。
请注意 ，整数点是具有整数坐标的点。
实现 Solution 类:
Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。
示例 1：
输入:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,1,1],[2,2,4,6]]],[],[],[],[],[]]输出:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]解释：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]提示：
1 <= rects.length <= 100
rects[i].length == 4
-10^9 <= ai < xi <= 10^9
-10^9 <= bi < yi <= 10^9
xi - ai <= 2000
yi - bi <= 2000
所有的矩形不重叠。
pick 最多被调用 10^4 次。思路分析
首先我们应该要先理解题目的题意，题目会给我们一个矩形数组，我们需要从矩形数组覆盖的点集合中随机获取一个点，所有满足要求的点必须等概率被返回。\
理解了题目要求后我们也就可以开始思考应该要怎么做了，最简单直接的做法当然是将所有矩形覆盖的点都统计出来，再随机从所有的点中抽取一个就可以了，但是让我们来看看数据量，数据的大小为：
-10^9 <= ai < xi <= 10^9
-10^9 <= bi < yi <= 10^9这样直接将所有的点统计出来必然会超出时间限制，所以这个做法不行，我们应该要换个思路再想想。我们可以先确定一个矩形，然后在从矩形中随机找一个点吗？当然可以，只要注意下面这一点就可以了：所有满足要求的点必须等概率被返回。所有的点被返回的概率相等，即矩形中的点数也多（矩形越大），该矩形被选中的概率越大。所以我们应该要先确认矩形被选中的概率，而后等概率抽取出一个矩形，在从矩形中抽取一个点，这样计算出的答案就是满足题意的，所有的点被返回的概率相等。
- 1、计算每个矩形被选中的概率
计算所有矩形覆盖面积的点数num，再统计每个矩形覆盖的点数map[i],则每个矩形被选中的概率为map[i] / num;
rects.map(item=>{
num += (item[2] - item[0] + 1) * (item[3] - item[1] + 1);
map.push(num);
});- 2、随机选择一个矩形
前面我们确定了所有矩形覆盖面积的点数，以及每个矩形的覆盖点数，所以我们可以从所有点数中随机抽取一个，然后在判断它位于哪个矩形中即可。
const num = this.getRandomNum(1,this.num);
let ind = 0;
while(!((this.map[ind - 1] || 0) <= num && num <= this.map[ind])) ind++;
const rect = this.rects[ind];- 3、从矩形中随机选择一个点
确认了选中的矩形之后，我们就可以直接从矩形中随机获取一个点了。
const x = this.getRandomNum(rect[0],rect[2]);
const y = this.getRandomNum(rect[1],rect[3]);
return [x,y];AC代码
/**
* @param {number[][]} rects
*/
var Solution = function(rects) {
this.rects = rects;
let num = 0;
let map = [];
rects.map(item=>{
num += (item[2] - item[0] + 1) * (item[3] - item[1] + 1);
map.push(num);
});
this.map = map;
this.num = num;
};
Solution.prototype.getRandomNum = function(minNum, maxNum) {
minNum = parseInt(minNum);
maxNum = parseInt(maxNum);
const res = Math.floor(Math.random() * (maxNum - minNum + 1)) + minNum;
return res;
};
Solution.prototype.pick = function() {
const num = this.getRandomNum(1,this.num);
let ind = 0;
while(!((this.map[ind - 1] || 0) <= num && num <= this.map[ind])) ind++;
const rect = this.rects[ind];
const x = this.getRandomNum(rect[0],rect[2]);
const y = this.getRandomNum(rect[1],rect[3]);
return [x,y];
};
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(rects)
* var param_1 = obj.pick()
*/说在后面
🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
