497 Random Point in Non-overlapping Rectangles
1. Question
Given a list ofnon-overlapping axis-aligned rectanglesrects
, write a functionpick
which randomly and uniformily picks aninteger pointin the space covered by the rectangles.
Note:
An integer point is a point that has integer coordinates.
A point on the perimeter of a rectangle is included in the space covered by the rectangles.
i
th rectangle =rects[i]
=[x1,y1,x2,y2]
, where[x1, y1]
are the integer coordinates of the bottom-left corner, and[x2, y2]
are the integer coordinates of the top-right corner.length and width of each rectangle does not exceed
2000
.1 <= rects.length <= 100
pick
return a point as an array of integer coordinates[p_x, p_y]
pick
is called at most10000
times.
Example 1:
Input:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:
[null,[4,1],[4,1],[3,3]]
Example 2:
Input:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution
's constructor has one argument, the array of rectanglesrects
.pick
has no arguments. Arguments are always wrapped with a list, even if there aren't any.
2. Implementation
(1) TreeMap
思路: 将累积面积的和放入TreeMap中,key是累积面积和,value是对应矩阵的index。调用pick()时,我们生成在[1, totalArea]的随机数,然后再通过treemap找到这个随机数所落入的累积面积和的区间,即找到最小的key,使得key对应的value大于等于随机数
class Solution {
TreeMap<Integer, Integer> map;
Random rand;
int[][] rects;
int totalArea;
public Solution(int[][] rects) {
this.rects = rects;
rand = new Random();
map = new TreeMap();
totalArea = 0;
for (int i = 0; i < rects.length; i++) {
int[] rect = rects[i];
// 坐标是从0开始,所以计算面积时,边长都要相应加1
totalArea += (rect[2] - rect[0] + 1) *(rect[3] - rect[1] + 1);
map.put(totalArea, i);
}
}
public int[] pick() {
// rand.nextInt(totalArea) 会返回(0, totalArea - 1)的随机数,所以rand.nextInt(totalArea) + 1保证
// 随机生成数在[1, totalArea]之间
int key = map.ceilingKey(rand.nextInt(totalArea) + 1);
return pickPointInRect(rects[map.get(key)]);
}
public int[] pickPointInRect(int[] rect) {
int x = rect[0] + rand.nextInt(rect[2] - rect[0] + 1);
int y = rect[1] + rand.nextInt(rect[3] - rect[1] + 1);
return new int[] {x, y};
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/
(2) Cumulative Sum Array
class Solution {
Random rand;
int[] area;
int totalArea;
int[][] rects;
public Solution(int[][] rects) {
this.rects = rects;
rand = new Random();
area = new int[rects.length];
totalArea = 0;
for (int i = 0; i < rects.length; i++) {
int curArea = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
if (i == 0) {
area[i] = curArea;
}
else {
area[i] = curArea + area[i - 1];
}
}
totalArea = area[rects.length - 1];
}
public int[] pick() {
int cumArea = rand.nextInt(totalArea) + 1;
int index = -1;
for (int i = 0; i < area.length; i++) {
if (cumArea <= area[i]) {
index = i;
break;
}
}
return pickPointInRect(rects[index]);
}
public int[] pickPointInRect(int[] rect) {
int x = rect[0] + rand.nextInt(rect[2] - rect[0] + 1);
int y = rect[1] + rand.nextInt(rect[3] - rect[1] + 1);
return new int[] {x, y};
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/
3. Time & Space Complexity
(1) TreeMap: solution(): O(nlogn), pick(): O(logn)
(2) One Pass: solution(): O(n), pick(): O(n)
Last updated
Was this helpful?