Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 497. Random Point in Non-overlapping Rectangles

---

題目：


方法：

將2D面積轉成1D線的表示方式，然後將這些1D線連接起來，這樣就可以用rand()選取想要的那個面積

解答：

class Solution {
private:
    vector<int> sum;
    vector<vector<int>> rects;

public:
    Solution(vector<vector<int>>& rects) {
        int total = 0;

        this->rects = rects;
        for (auto r : rects) {
            int x = (r[2] - r[0]) + 1;
            int y = (r[3] - r[1]) + 1;

            total += (x * y);
            sum.push_back(total);
        }
    }
    
    vector<int> pick() {
        int total = sum.back();
    
        int k = (rand() % total) + 1;
        int idx = lower_bound(sum.begin(), sum.end(), k) - sum.begin();
        auto& r = rects[idx];

        int x1 = r[0];
        int y1 = r[1];
        int x2 = r[2];
        int y2 = r[3];

        int x = x1 + (rand() % (x2 - x1 + 1));
        int y = y1 + (rand() % (y2 - y1 + 1));

        return { x, y };
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(rects);
 * vector<int> param_1 = obj->pick();
 */