题目
给定一个由非重叠的轴对齐矩形的数组 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],[1,0,3,0]]],[],[],[],[],[]]
输出:
[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
次。
解题
方法一:水塘抽样
思路
总体思路:现在所有矩形中随机抽出一个矩形,再在该矩形中随机抽出 x、y 坐标即可。
随机抽出矩形:
- 假设共有 n 个矩形,那么其中某个矩形 k 被选中的概率并不是
- 而是 也即
这里我们遍历 rects
数组,维护一个被抽到的矩形下标 idx
,一个总面积 total
:
- 对于每个矩形算出其面积 (
curr
) - 然后把面积加入到总面积中
total += curr
- 如果 那么就随机到了当前遍历到的矩形,把
idx
置为当前矩形的索引 - 由于每次遍历都会抽取矩形,那么这次遍历抽取到的矩形被保留的概率就是
完成遍历后一定可以随机的选出一个矩形 rects[idx]
。
取出该矩形左下角的点 ,右上角的点
返回
代码
class Solution {
private Random rand;
private int[][] rects;
public Solution(int[][] _rects) {
rand = new Random();
rects = _rects;
}
public int[] pick() {
int idx = -1, total = 0;
for (int i = 0; i < rects.length; i++) {
int curr = (rects[i][2] - rects[i][0] + 1) *
(rects[i][3] - rects[i][1] + 1);
total += curr;
if (rand.nextInt(total) < curr) idx = i;
}
int[] rect = rects[idx];
int a = rect[0], b = rect[1], x = rect[2], y = rect[3];
return new int[]{a + rand.nextInt(x - a + 1), b + rand.nextInt(y - b + 1)};
}
}
评论区