每日一题—LeetCode497—非重叠矩形中的随机点-前缀和-二分

原题链接

Note：

面积越大，抽中的概率越高，从矩形中抽样好抽，横纵坐标独立的，都随机生成一下就行
但是要先确定是哪一个矩形

展成一维的情况，用一个前缀和数组来记录面积和
每次随机生成一个数，他会落到这个一维的数组中，用二分去查找落得对应位置是哪一个矩形

前缀和数组是下标从1开始的，那么二分的范围就是1 ~ n
二分出来的结果减一 才能对应到给的输入的矩阵数组里

代码如下：

class Solution {
public:
    int n;
    vector<vector<int>> rects;
    vector<int> sum;
    Solution(vector<vector<int>>& _rects) {
        sum.push_back(0);
        rects = _rects;
        n = rects.size();
        for(auto r: rects){
            int w = r[2] - r[0] + 1, h = r[3] - r[1] + 1;
            sum.push_back(sum.back() + w * h);
        }
    }
    
    vector<int> pick() {
        int k = rand() % sum.back() + 1;
        int l = 1, r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(sum[mid] >= k)    r = mid;
            else    l = mid + 1;
        }
        auto t = rects[r - 1];
        int dx = t[2] - t[0] + 1, dy = t[3] - t[1] + 1;
        return {rand() % dx + t[0], rand() % dy + t[1]};

    }
};

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