497 Random Point in Non-overlapping Rectangles

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.An integer point is a point that has integer coordinates. 
2.A point on the perimeter of a rectangle is included in the space covered by the rectangles. 
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.length and width of each rectangle does not exceed2000.
5.1 <= rects.length <= 100
6.pickreturn a point as an array of integer coordinates [p_x, p_y]
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)

616 Add Bold Tag in String

544 Output Contest Matches

Last modified 2yr ago

Copy link

Contents

497. Random Point in Non-overlapping Rectangles

1. Question

2. Implementation

3. Time & Space Complexity

497. Random Point in Non-overlapping Rectangles​

1. Question

2. Implementation

3. Time & Space Complexity

497. Random Point in Non-overlapping Rectangles