Google
497 Random Point in Non-overlapping Rectangles

1. Question

Given a list ofnon-overlapping axis-aligned rectanglesrects, write a functionpickwhich randomly and uniformily picks aninteger pointin the space covered by the rectangles.
Note:
  1. 1.
    An integer point is a point that has integer coordinates.
  2. 2.
    A point on the perimeter of a rectangle is included in the space covered by the rectangles.
  3. 3.
    ith 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.
  4. 4.
    length and width of each rectangle does not exceed2000.
  5. 5.
    1 <= rects.length <= 100
  6. 6.
    pickreturn a point as an array of integer coordinates [p_x, p_y]
  7. 7.
    pickis called at most10000times.
Example 1:
1
Input:
2
3
["Solution","pick","pick","pick"]
4
5
[[[[1,1,5,5]]],[],[],[]]
6
Output:
7
8
[null,[4,1],[4,1],[3,3]]
Copied!
Example 2:
1
Input:
2
3
["Solution","pick","pick","pick","pick","pick"]
4
5
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
6
Output:
7
8
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
Copied!
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大于等于随机数
1
class Solution {
2
TreeMap<Integer, Integer> map;
3
Random rand;
4
int[][] rects;
5
int totalArea;
6
7
public Solution(int[][] rects) {
8
this.rects = rects;
9
rand = new Random();
10
map = new TreeMap();
11
totalArea = 0;
12
13
for (int i = 0; i < rects.length; i++) {
14
int[] rect = rects[i];
15
// 坐标是从0开始,所以计算面积时,边长都要相应加1
16
totalArea += (rect[2] - rect[0] + 1) *(rect[3] - rect[1] + 1);
17
map.put(totalArea, i);
18
}
19
}
20
21
public int[] pick() {
22
// rand.nextInt(totalArea) 会返回(0, totalArea - 1)的随机数,所以rand.nextInt(totalArea) + 1保证
23
// 随机生成数在[1, totalArea]之间
24
int key = map.ceilingKey(rand.nextInt(totalArea) + 1);
25
return pickPointInRect(rects[map.get(key)]);
26
}
27
28
public int[] pickPointInRect(int[] rect) {
29
int x = rect[0] + rand.nextInt(rect[2] - rect[0] + 1);
30
int y = rect[1] + rand.nextInt(rect[3] - rect[1] + 1);
31
return new int[] {x, y};
32
}
33
}
34
35
/**
36
* Your Solution object will be instantiated and called as such:
37
* Solution obj = new Solution(rects);
38
* int[] param_1 = obj.pick();
39
*/
Copied!
(2) Cumulative Sum Array
1
class Solution {
2
Random rand;
3
int[] area;
4
int totalArea;
5
int[][] rects;
6
7
public Solution(int[][] rects) {
8
this.rects = rects;
9
rand = new Random();
10
area = new int[rects.length];
11
totalArea = 0;
12
13
for (int i = 0; i < rects.length; i++) {
14
int curArea = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
15
if (i == 0) {
16
area[i] = curArea;
17
}
18
else {
19
area[i] = curArea + area[i - 1];
20
}
21
}
22
totalArea = area[rects.length - 1];
23
}
24
25
public int[] pick() {
26
int cumArea = rand.nextInt(totalArea) + 1;
27
int index = -1;
28
29
for (int i = 0; i < area.length; i++) {
30
if (cumArea <= area[i]) {
31
index = i;
32
break;
33
}
34
}
35
return pickPointInRect(rects[index]);
36
}
37
38
public int[] pickPointInRect(int[] rect) {
39
int x = rect[0] + rand.nextInt(rect[2] - rect[0] + 1);
40
int y = rect[1] + rand.nextInt(rect[3] - rect[1] + 1);
41
return new int[] {x, y};
42
}
43
}
44
45
/**
46
* Your Solution object will be instantiated and called as such:
47
* Solution obj = new Solution(rects);
48
* int[] param_1 = obj.pick();
49
*/
Copied!

3. Time & Space Complexity

(1) TreeMap: solution(): O(nlogn), pick(): O(logn)
(2) One Pass: solution(): O(n), pick(): O(n)