題目： LeetCode - 497. Random Point in Non-overlapping Rectangles

題目說明

給一個陣列代表矩形的左下角座標及右上角座標，所有矩形都不會重疊。要求完成一個函式能隨機取一個在矩形內的點。

解題思路

  • Solution(vector<vector<int>>& rects)： 先使用一個陣列紀錄到目前的矩形總共有多少的點，方便做隨機取樣。
  • vector<int> pick()： 隨機取一個小於點的數量的數，接著找出它位於第幾個矩形，接著在該矩形內隨機取一點即可。

參考解法

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
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    Solution(vector<vector<int>>& rects) : _rects(rects) {
        for(int i = 0, count = 0; i < rects.size(); ++i)
            count += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1), dots.emplace_back(count);
        srand(time(nullptr));
    }
    
    vector<int> pick() {
        int pos = lower_bound(dots.begin(), dots.end(), rand() % dots.back() + 1) - dots.begin();
        int length = _rects[pos][2] - _rects[pos][0] + 1, width = _rects[pos][3] - _rects[pos][1] + 1;
        return {_rects[pos][0] + rand() % length, _rects[pos][1] + rand() % width};
    }
private:
    vector<vector<int>> _rects;
    vector<int> dots;
};