Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/497.html
497. Random Point in Non-overlapping Rectangles (Medium)
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.
Related Topics:
Binary Search, Random
Similar Questions:
Solution 1. Binary Search
// OJ: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
// Time:
// Solution: O(N)
// pick: O(logN)
// Space: O(N)
class Solution {
vector<vector<int>> A;
vector<int> size;
int total = 0;
public:
Solution(vector<vector<int>>& rects) : A(rects) {
for (auto &r : A) size.push_back(total += (r[3] - r[1] + 1) * (r[2] - r[0] + 1));
}
vector<int> pick() {
int r = rand() % total;
int i = upper_bound(begin(size), end(size), r) - begin(size);
r -= i > 0 ? size[i - 1] : 0;
int w = A[i][3] - A[i][1] + 1;
return { A[i][0] + r / w, A[i][1] + r % w };
}
};
-
class Solution { int rectsCount; int[][] rects; int[] accumulatedPoints; int pointsCount; public Solution(int[][] rects) { rectsCount = rects.length; this.rects = rects; accumulatedPoints = new int[rectsCount]; for (int i = 0; i < rectsCount; i++) { int[] rect = rects[i]; int points = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1); accumulatedPoints[i] = points; pointsCount += points; } for (int i = 1; i < rectsCount; i++) accumulatedPoints[i] += accumulatedPoints[i - 1]; } public int[] pick() { int pointsPosition = (int) (Math.random() * pointsCount); int index = 0; for (int i = 0; i < rectsCount; i++) { if (accumulatedPoints[i] > pointsPosition) { index = i; break; } } int[] rect = rects[index]; int xMin = rect[0], xMax = rect[2]; int yMin = rect[1], yMax = rect[3]; int randomX = xMin + (int) (Math.random() * (xMax - xMin + 1)); int randomY = yMin + (int) (Math.random() * (yMax - yMin + 1)); int[] randomPoint = {randomX, randomY}; return randomPoint; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(rects); * int[] param_1 = obj.pick(); */ ############ class Solution { private int[] s; private int[][] rects; private Random random = new Random(); public Solution(int[][] rects) { int n = rects.length; s = new int[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1); } this.rects = rects; } public int[] pick() { int n = rects.length; int v = 1 + random.nextInt(s[n]); int left = 0, right = n; while (left < right) { int mid = (left + right) >> 1; if (s[mid] >= v) { right = mid; } else { left = mid + 1; } } int[] rect = rects[left - 1]; return new int[] {rect[0] + random.nextInt(rect[2] - rect[0] + 1), rect[1] + random.nextInt(rect[3] - rect[1] + 1)}; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(rects); * int[] param_1 = obj.pick(); */
-
// OJ: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/ // Time: // Solution: O(N) // pick: O(logN) // Space: O(N) class Solution { vector<vector<int>> A; vector<int> size; int total = 0; public: Solution(vector<vector<int>>& rects) : A(rects) { for (auto &r : A) size.push_back(total += (r[3] - r[1] + 1) * (r[2] - r[0] + 1)); } vector<int> pick() { int r = rand() % total; int i = upper_bound(begin(size), end(size), r) - begin(size); r -= i > 0 ? size[i - 1] : 0; int w = A[i][3] - A[i][1] + 1; return { A[i][0] + r / w, A[i][1] + r % w }; } };
-
class Solution: def __init__(self, rects: List[List[int]]): self.rects = rects self.s = [0] * len(rects) for i, (x1, y1, x2, y2) in enumerate(rects): self.s[i] = self.s[i - 1] + (x2 - x1 + 1) * (y2 - y1 + 1) def pick(self) -> List[int]: v = random.randint(1, self.s[-1]) idx = bisect_left(self.s, v) x1, y1, x2, y2 = self.rects[idx] return [random.randint(x1, x2), random.randint(y1, y2)] # Your Solution object will be instantiated and called as such: # obj = Solution(rects) # param_1 = obj.pick() ############ class Solution(object): def __init__(self, rects): """ :type rects: List[List[int]] """ self.rects = rects self.N = len(rects) areas = [(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects] self.preSum = [0] * self.N self.preSum[0] = areas[0] for i in range(1, self.N): self.preSum[i] = self.preSum[i - 1] + areas[i] self.total = self.preSum[-1] def pickRect(self): rand = random.randint(0, self.total - 1) return bisect.bisect_right(self.preSum, rand) def pickPoint(self, rect): x1, y1, x2, y2 = rect x = random.randint(x1, x2) y = random.randint(y1, y2) return x, y def pick(self): """ :rtype: List[int] """ rectIndex = self.pickRect() rect = self.rects[rectIndex] return self.pickPoint(rect) # Your Solution object will be instantiated and called as such: # obj = Solution(rects) # param_1 = obj.pick()
-
type Solution struct { s []int rects [][]int } func Constructor(rects [][]int) Solution { n := len(rects) s := make([]int, n+1) for i, v := range rects { s[i+1] = s[i] + (v[2]-v[0]+1)*(v[3]-v[1]+1) } return Solution{s, rects} } func (this *Solution) Pick() []int { n := len(this.rects) v := 1 + rand.Intn(this.s[len(this.s)-1]) left, right := 0, n for left < right { mid := (left + right) >> 1 if this.s[mid] >= v { right = mid } else { left = mid + 1 } } rect := this.rects[left-1] x, y := rect[0]+rand.Intn(rect[2]-rect[0]+1), rect[1]+rand.Intn(rect[3]-rect[1]+1) return []int{x, y} }