497. Random Point in Non-overlapping Rectangles

理解
猛一看这个题，没看懂，写的时候很懵逼；
从一堆给定的non-overlapping rectangles实现randomly and uniformily 的pick（）方法，每次pick的坐标要足够随机和均匀分布；

思路
1、因为rectangles的非覆盖的，用每个rectangles的area组成一个一维数组，首先从这个一维数组中取随机rand();
2、对于第1步中的随机数，查找属于哪个rectangle, 然后在查找到的rectangle中再随机坐标；

重点
1、rand()方法的使用： rand() % M;
2、rand() % M的结果范围是 [0，M-1], 双闭区间;
3、从area组成的一维数组中获得随机数，目标结果为 [1, N] , 此处的用法为 rand() % N + 1;
4、从选定的rectangle中获取随机坐标，目标结果是 [0 ~ px, 0 ~ py], 此处的用法是 rand() % (px + 1), rand() % (py + 1) ;

代码

class Solution {
public:
    vector<vector<int>> rect;
    vector<int> areas;
    int total;
    Solution(vector<vector<int>>& rects) {
        rect = rects;
        int n = rects.size();
        areas.resize(n);
        for(int i=0; i<n; i++){
            int x1 = rects[i][0];
            int y1 = rects[i][1];
            int x2 = rects[i][2];
            int y2 = rects[i][3];
            if (i == 0){
                areas[i] = (x2 - x1 + 1) * (y2 - y1 + 1);
            }else{
                areas[i] = areas[i-1] + (x2 - x1 + 1) * (y2 - y1 + 1);
            }
        }
        total = areas[n-1];

    }
    
    vector<int> pick() {
        int which = rand() % total + 1;
        int i;
        for(i=0; i<areas.size(); i++){
            if(which <= areas[i])
                break;
        }
        int x1 = rect[i][0];
        int y1 = rect[i][1];
        int x2 = rect[i][2];
        int y2 = rect[i][3];       
        int px = rand() % (x2 - x1 + 1) + x1;
        int py = rand() % (y2 - y1 + 1) + y1;

        return {px, py};
    }
};

优化
对于pick函数，按顺序查找which 所属的areas时，可以使用binary search进行优化，代码如下：

    vector<int> pick() {
        int which = rand() % total + 1;
        auto it = lower_bound(areas.begin(), areas.end(), which);
        int i = it - areas.begin();
        // int i;
        // for(i=0; i<areas.size(); i++){
        //     if(which <= areas[i])
        //         break;
        // }
        int x1 = rect[i][0];
        int y1 = rect[i][1];
        int x2 = rect[i][2];
        int y2 = rect[i][3];       
        int px = rand() % (x2 - x1 + 1) + x1;
        int py = rand() % (y2 - y1 + 1) + y1;

        return {px, py};
    }

cooboos

497. Random Point in Non-overlapping Rectangles