Random Point in Non-overlapping Rectangles (M)
題目
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:
- 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.
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.- length and width of each rectangle does not exceed
2000. 1 <= rects.length <= 100pickreturn a point as an array of integer coordinates[p_x, p_y]pickis called at most10000times.
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 rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.
題意
給定若干個互不重疊的矩形，要求每次從這些矩形覆寫的區域中均勻隨機地選出一個點，
思路
我們不能單純的給每個矩形編號，隨機選一個編號再從對應的矩形中隨機選一個點，因為這樣不能保證每個點被選到的概率是一樣的，應該以每個矩形覆寫的面積來確定它被選到的概率，具體操作為：遍歷所有矩形，每次累加當前矩形包含的點數(即面積)，并以此作為當前矩形的編號，可以得到一個類似數軸的圖：
記總點數為area，從區間[1, area]中隨機選一個點p，那么對應的矩形編號就是p所在的顏色方塊的右端點，再在這個矩形中隨機選出一個點，以這種方式選取矩形能夠保證每個點被選到的概率是一樣的，
代碼實作
Java
class Solution {
private Random random;
// 為了方便使用了TreeMap，也可以用HashMap結合二分搜索找key
private TreeMap<Integer, int[]> map;
private int area;
public Solution(int[][] rects) {
random = new Random();
map = new TreeMap<>();
for (int[] rect : rects) {
area += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
map.put(area, rect);
}
}
public int[] pick() {
int[] rect = map.get(map.ceilingKey(random.nextInt(area) + 1));
int x = rect[0] + random.nextInt(rect[2] - rect[0] + 1);
int y = rect[1] + random.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();
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145108.html
標籤：其他
上一篇：單調佇列