497. 非重叠矩形中的随机点

原题链接：497. 非重叠矩形中的随机点

 

solution:

        ① 计算所有矩形中点的数量
        ② 利用rand()函数随机获取一个值
        ③ 根据②获取的值,找到对应的矩形
        ④ 再从矩形中找到对应的点

class Solution {
public:
    vector<vector<int>> rects;
    int *area;   //保存每个矩形中的点
    int n;
    int sum;
    Solution(vector<vector<int>>& rects) {
        this->rects = rects;
        n = rects.size();
        sum = 0;
        area = (int *)malloc(sizeof(int) * n);
        for(int i = 0;i < n;i++) {
            area[i] = ((rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1));
            sum += area[i];
        }
    }
    
    vector<int> pick() {
        int rnd = rand() % sum; //在所有的点中随机寻找一个点
        int i,pos;
        //找到点对应的矩形
        for(i = 0,pos = 0;i < n;i++) {
            if(pos + area[i] > rnd) break;
            pos += area[i];
        }
        rnd -= pos;
        //在找到的矩形中找到具体的点
        int x = rects[i][0] + rnd % (rects[i][2] - rects[i][0] + 1);
        int y = rects[i][1] + rnd / (rects[i][2] - rects[i][0] + 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();
 */