https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
Given a list of non-overlapping axis-aligned rectangles
http://www.cnblogs.com/grandyang/p/9752145.html
http://www.programmersought.com/article/7189227202/
http://hehejun.blogspot.com/2018/07/leetcoderandom-point-in-non-overlapping.html
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 anyhttp://www.programmersought.com/article/7189227202/
Since it is seen that there is no overlap, and it is apparent that the probability that the integer points inside the same rectangle are selected is the same, the probability that the points inside the different rectangles are selected is equal to the area of the rectangle. Then we definitely think of first randomly selecting a rectangle according to the area, and then randomly selecting an integer point in the rectangle is ok.
So, how do you choose points according to the area? then528. Random Pick with WeightIt came in handy. The idea is to convert the PDF to CDF, then randomly select points and find the upper_bound of this point. The overall idea is still quite new, so you must first make 528 questions to do this.
The practice of this question is basically the same. I submitted the error several times, and finally found the reason by thinking about the test cases given by the topic. Looking at the second test case given by the title, there is a rectangle.
[1, 0, 3, 0]Is this area not 0? But the topic also thinks this is a rectangle with 3 integer points. So the way to find the area has to be changed. This question is not simply to find the area of the rectangle, but to find the number of integer points in the rectangle. The calculation method is(x2 - x1 + 1) * (y2 - y1 + 1)。
The time complexity of initialization is O(N), the time complexity of each query is O(logN), and the space complexity is O(N).
https://blog.csdn.net/fuxuemingzhu/article/details/83098201
给出了几个不重叠的长方形，按照覆盖面积随机在这些长方形中随机取横纵坐标都是整数的点。
既然看到不重叠了，而且明显同一长方形内部的整数点被选择的概率相同，不同长方形内部的点被选择的概率等于该长方形的面积。那么我们肯定想到的是首先按照面积随机选择一个长方形，然后再在长方形中随机选择一个整数点就ok了。
所以，怎么按照面积选点呢？于是528. Random Pick with Weight就派到用场了。思想是把PDF转换成CDF，然后再随机选择点，找到这个点的upper_bound。整体的思路还是挺新颖的，所以一定得先把528题做出来才能做这个题。
这个题的做法基本一致，我提交错误好几次，最后通过思考题目给出的测试用例找到了原因。看题目给的第二个测试用例中，有个长方形是[1, 0, 3, 0]，这个面积不是0么？但是题目也认为这个是有3个整数点的长方形。所以求面积的方式得改啊，这个题不是简单的求长方形的面积，而是求长方形中整数点的个数，计算方式是(x2 - x1 + 1) * (y2 - y1 + 1)。
初始化的时间复杂度是O(N)，每次查询的时间复杂度是O(logN)，空间复杂度是O(N)。
这道题在论坛上的主流解法其实是这个，我们用TreeMap来建立当前遍历过的矩形面积之和跟该矩形位置之间的映射。然后当我们求出所有的矩形面积之和后，我们随机生成一个值，然后在TreeMap中找到第一个大于这个值的矩形，这里博主还是有疑问，为啥不能直接随机矩形的位置，而是非要跟面积扯上关系。之后的步骤就跟上面的没啥区别了
TreeMap<Integer, Integer> map;
int[][] arrays;
int sum;
Random rnd= new Random();
public Solution(int[][] rects) {
arrays = rects;
map = new TreeMap<>();
sum = 0;
for(int i = 0; i < rects.length; i++) {
int[] rect = rects[i];
// the right part means the number of points of this rectangle, rather than its area
// coz ractangles gonna get picked by the num of points
sum += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
map.put(sum, i);
}
}
public int[] pick() {
// nextInt(sum) returns a num in [0, sum -1]. After added by 1, it becomes [1, sum]
int c = map.ceilingKey( rnd.nextInt(sum) + 1);
return pickInRect(arrays[map.get(c)]);
}
private int[] pickInRect(int[] rect) {
int left = rect[0], right = rect[2], bot = rect[1], top = rect[3];
return new int[]{left + rnd.nextInt(right - left + 1), bot + rnd.nextInt(top - bot + 1) };
}
这道题给了我们一些非重叠的矩形，让我们返回一个这些矩形中的一个随机的点。那么博主的第一直觉就是首先要在这些矩形中随机挑出来一个，然后在这个随机的矩形中再随机生成一个点，通过随机生成一个长和宽即可。博主最开始想到的方法是用rand随机生成一个 [0, n) 范围内的数字，n为输入矩形的个数，这样就得到了一个随机的矩形。但是这种方法貌似行不通，会跪在一个很长的输入测试数据。这使得博主比较困惑了，没有想出原因是为何，有哪位看官大神们知道的，麻烦留言告知博主哈！哈，已经知道了，参见评论区二楼留言～ 论坛上的解法有一种是用水塘抽样Reservoir Sampling的方法的，LeetCode之前有过几道需要用这种方法的题目Random Pick Index，Shuffle an Array和Linked List Random Node。这里我们使用其来随机出一个矩形，做法是遍历所有的矩形，用变量sumArea来计算当前遍历过的所有矩形面积之和，然后变量area是当前遍历的矩形的面积，然后我们在当前所有矩形面积之和内随机生成一个值，如果这个值小于area，那么选择当前的矩阵为随机矩形。这里相当于一个大小为area的水塘，在这个值之内的话，就更换selected。这个方法是没啥问题，但是博主还是没想通为啥不能直接随机生成矩形的index。当我们拿到随机矩形后，之后就随机出宽和高返回即可
Solution(vector<vector<int>> rects) { _rects = rects; } vector<int> pick() { int sumArea = 0; vector<int> selected; for (auto rect : _rects) { int area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1); sumArea += area; if (rand() % sumArea < area) selected = rect; } int x = rand() % (selected[2] - selected[0] + 1) + selected[0]; int y = rand() % (selected[3] - selected[1] + 1) + selected[1]; return {x, y}; }
http://hehejun.blogspot.com/2018/07/leetcoderandom-point-in-non-overlapping.html
