题目

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in 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 exceed 2000.
  5. 1 <= rects.length <= 100
  6. pick return a point as an array of integer coordinates [p_x, p_y]
  7. pick is called at most 10000 times.

Example 1:

  1. Input: 
  2. ["Solution","pick","pick","pick"]
  3. [[[[1,1,5,5]]],[],[],[]]
  4. Output: 
  5. [null,[4,1],[4,1],[3,3]]

Example 2:

  1. Input: 
  2. ["Solution","pick","pick","pick","pick","pick"]
  3. [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
  4. Output: 
  5. [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 rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

题意

给定若干个互不重叠的矩形，要求每次从这些矩形覆盖的区域中均匀随机地选出一个点。

思路

我们不能单纯的给每个矩形编号，随机选一个编号再从对应的矩形中随机选一个点，因为这样不能保证每个点被选到的概率是一样的。应该以每个矩形覆盖的面积来确定它被选到的概率。具体操作为：遍历所有矩形，每次累加当前矩形包含的点数(即面积)，并以此作为当前矩形的编号，可以得到一个类似数轴的图：
image.png
记总点数为area，从区间[1, area]中随机选一个点p，那么对应的矩形编号就是p所在的颜色方块的右端点。再在这个矩形中随机选出一个点。以这种方式选取矩形能够保证每个点被选到的概率是一样的。

代码实现

Java

  1. class Solution {
  2.     private Random random;
  3.     // 为了方便使用了TreeMap，也可以用HashMap结合二分搜索找key
  4.     private TreeMap<Integer, int[]> map;
  5.     private int area;
  7.     public Solution(int[][] rects) {
  8.         random = new Random();
  9.         map = new TreeMap<>();
  10.         for (int[] rect : rects) {
  11.             area += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
  12.             map.put(area, rect);
  13.         }
  14.     }
  16.     public int[] pick() {
  17.         int[] rect = map.get(map.ceilingKey(random.nextInt(area) + 1));
  18.         int x = rect[0] + random.nextInt(rect[2] - rect[0] + 1);
  19.         int y = rect[1] + random.nextInt(rect[3] - rect[1] + 1);
  20.         return new int[] { x, y };
  21.     }
  22. }
  24. /**
  25.  * Your Solution object will be instantiated and called as such: Solution obj =
  26.  * new Solution(rects); int[] param_1 = obj.pick();
  27.  */