Problem
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.
Solution: Binary Search
Same as LeetCode 880. Random Pick with Weight
Use area of the rectangles as weights.
Time complexity: Init: O(n) Pick: O(logn)
Space complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Running time: 92 ms class Solution { public: Solution(vector<vector<int>> rects): rects_(std::move(rects)) { sums_ = vector<int>(rects_.size()); for (int i = 0; i < rects_.size(); ++i) { sums_[i] = (rects_[i][2] - rects_[i][0] + 1) * (rects_[i][3] - rects_[i][1] + 1); if (i > 0) sums_[i] += sums_[i - 1]; } } vector<int> pick() { const int s = nextInt(sums_.back()) + 1; int index = lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin(); const auto& rect = rects_[index]; return {rect[0] + nextInt(rect[2] - rect[0] + 1), rect[1] + nextInt(rect[3] - rect[1] + 1)}; } private: vector<int> sums_; vector<vector<int>> rects_; // Returns a random int in [0, n - 1] int nextInt(int n) { return rand() / static_cast<double>(RAND_MAX) * n; } }; |