[LeetCode] Random Point in Non-overlapping Rectangles 非重叠矩形中的随机点
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.
i
th 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 <= 100
pick
return a point as an array of integer coordinates[p_x, p_y]
pick
is called at most10000
times.
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.
这道题给了我们一些非重叠的矩形,让我们返回一个这些矩形中的一个随机的点。那么博主的第一直觉就是首先要在这些矩形中随机挑出来一个,然后在这个随机的矩形中再随机生成一个点,通过随机生成一个长和宽即可。博主最开始想到的方法是用rand随机生成一个 [0, n) 范围内的数字,n为输入矩形的个数,这样就得到了一个随机的矩形。但是这种方法貌似行不通,会跪在一个很长的输入测试数据。这使得博主比较困惑了,没有想出原因是为何,有哪位看官大神们知道的,麻烦留言告知博主哈!哈,已经知道了,参见评论区二楼留言~ 论坛上的解法有一种是用水塘抽样Reservoir Sampling的方法的,LeetCode之前有过几道需要用这种方法的题目 Random Pick Index,Shuffle an Array 和 Linked List Random Node。这里我们使用其来随机出一个矩形,做法是遍历所有的矩形,用变量sumArea来计算当前遍历过的所有矩形面积之和,然后变量area是当前遍历的矩形的面积(注意这里不是严格意义上的面积,而是该区域内整数坐标的点的个数,所以长宽相乘的时候都要加1),然后我们在当前所有矩形面积之和内随机生成一个值,如果这个值小于area,那么选择当前的矩阵为随机矩形。这里相当于一个大小为area的水塘,在这个值之内的话,就更换selected。这个方法是没啥问题,但是博主还是没想通为啥不能直接随机生成矩形的index。当我们拿到随机矩形后,之后就随机出宽和高返回即可,参见代码如下:
解法一:
class Solution { public: 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}; } private: vector<vector<int>> _rects; };
这道题在论坛上的主流解法其实是这个,我们用TreeMap来建立当前遍历过的矩形面积之和跟该矩形位置之间的映射。然后当我们求出所有的矩形面积之和后,我们随机生成一个值,然后在TreeMap中找到第一个大于这个值的矩形,这里博主还是有疑问,为啥不能直接随机矩形的位置,而是非要跟面积扯上关系。之后的步骤就跟上面的没啥区别了,参见代码如下:
解法二:
class Solution { public: Solution(vector<vector<int>> rects) { _rects = rects; _totalArea = 0; for (auto rect : rects) { _totalArea += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1); _areaToIdx.insert({_totalArea, _areaToIdx.size()}); } } vector<int> pick() { int val = rand() % _totalArea; int idx = _areaToIdx.upper_bound(val)->second; int width = _rects[idx][2] - _rects[idx][0] + 1; int height = _rects[idx][3] - _rects[idx][1] + 1; return {rand() % width + _rects[idx][0], rand() % height + _rects[idx][1]}; } private: vector<vector<int>> _rects; int _totalArea; map<int, int> _areaToIdx; };
类似题目:
Generate Random Point in a Circle
参考资料:
https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
相关文章
- leetcode 之Swap Nodes in Pairs(21)
- leetcode 之Search in Rotated Sorted Array(四)
- Java实现 LeetCode 784 字母大小写全排列(DFS)
- Java实现 LeetCode 766 托普利茨矩阵(暴力)
- Java实现 LeetCode 677 键值映射(字典树)
- Java实现 LeetCode 590 N叉树的后序遍历(遍历树,迭代法)
- Java实现 LeetCode 535 TinyURL 的加密与解密(位运算加密)
- Java实现 LeetCode 397 整数替换
- Java实现 LeetCode 230 2的幂
- Java实现 LeetCode 172 阶乘后的零
- [LeetCode] Longest Increasing Path in a Matrix
- [LeetCode] Rotate Array
- Matlab:成功解决In an assignment A(I)=B,the number of elements in B and I must be the same
- LeetCode——Populating Next Right Pointers in Each Node II
- [LeetCode] Search in Rotated Sorted Array II [36]
- Leetcode--Reverse Nodes in k-Group
- 【LeetCode】Balanced Binary Tree 解题报告
- LeetCode:Find Minimum in Rotated Sorted Array
- leetcode Kth Largest Element in a Stream——要熟悉heapq使用
- leetcode 671. Second Minimum Node In a Binary Tree
- leetcode 237. Delete Node in a Linked List
- leetcode 637. Average of Levels in Binary Tree
- leetcode 476. Number Complement
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 283. 移动零