題目: 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
| 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; };
|