给定一个由非重叠的轴对齐矩形的数组 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], [1, -1], [-1, -2], [-2, -2], [0, 0]] 解释: 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
-109 <= ai < xi <= 109
-109 <= bi < yi <= 109
xi - ai <= 2000
yi - bi <= 2000
- 所有的矩形不重叠。
pick
最多被调用104
次。
方法一:前缀和 + 二分查找
将矩形面积求前缀和
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.s = [0] * len(rects)
for i, (x1, y1, x2, y2) in enumerate(rects):
self.s[i] = self.s[i - 1] + (x2 - x1 + 1) * (y2 - y1 + 1)
def pick(self) -> List[int]:
v = random.randint(1, self.s[-1])
idx = bisect_left(self.s, v)
x1, y1, x2, y2 = self.rects[idx]
return [random.randint(x1, x2), random.randint(y1, y2)]
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
class Solution {
private int[] s;
private int[][] rects;
private Random random = new Random();
public Solution(int[][] rects) {
int n = rects.length;
s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
}
this.rects = rects;
}
public int[] pick() {
int n = rects.length;
int v = 1 + random.nextInt(s[n]);
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (s[mid] >= v) {
right = mid;
} else {
left = mid + 1;
}
}
int[] rect = rects[left - 1];
return new int[] {rect[0] + random.nextInt(rect[2] - rect[0] + 1),
rect[1] + random.nextInt(rect[3] - rect[1] + 1)};
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/
class Solution {
public:
vector<int> s;
vector<vector<int>> rects;
Solution(vector<vector<int>>& rects) {
int n = rects.size();
s.resize(n + 1);
for (int i = 0; i < n; ++i) s[i + 1] = s[i] + (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
this->rects = rects;
srand(time(nullptr));
}
vector<int> pick() {
int n = rects.size();
int v = 1 + rand() % s[n];
int idx = lower_bound(s.begin(), s.end(), v) - s.begin();
auto& rect = rects[idx - 1];
int x = rect[0] + rand() % (rect[2] - rect[0] + 1);
int y = rect[1] + rand() % (rect[3] - rect[1] + 1);
return {x, y};
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(rects);
* vector<int> param_1 = obj->pick();
*/
type Solution struct {
s []int
rects [][]int
}
func Constructor(rects [][]int) Solution {
n := len(rects)
s := make([]int, n+1)
for i, v := range rects {
s[i+1] = s[i] + (v[2]-v[0]+1)*(v[3]-v[1]+1)
}
return Solution{s, rects}
}
func (this *Solution) Pick() []int {
n := len(this.rects)
v := 1 + rand.Intn(this.s[len(this.s)-1])
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if this.s[mid] >= v {
right = mid
} else {
left = mid + 1
}
}
rect := this.rects[left-1]
x, y := rect[0]+rand.Intn(rect[2]-rect[0]+1), rect[1]+rand.Intn(rect[3]-rect[1]+1)
return []int{x, y}
}