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

关键词： 前缀和 二分 概率

题目描述

给定多个不重叠的矩形(矩形的边与坐标轴平行)
对于每个矩形中的点(x,y都为整数)都有相同的概率在pick接口中获取

思路分析

思考: 是什么概率类型?

样本空间有限，是古典概型

思考: 如何模拟均匀分布?

伪随机生成函数即可

思考：得到的随机数与点如何对应?

暴力地保存每个点肯定不合适，不妨先确定是哪个矩形内，再确定矩形内的点

由以上分析得：

1. 等概率获取表明每个区域获取的可能性与矩形区域中的样本点的数目有关

2. 总的可能样本数目是所有区域的样本数目之和

​ 设矩形总个数为,矩形面积分别为,总的样本数目为,那么每个矩形区域被选择到的概率分别为：那么可以选取一个区间的一个随机数,区间表示矩形,区间表示矩形,依次类推。这个过程就得到了选取哪个矩形区域。

​ 由于每个矩形区域中的点被选取的概率相同，不妨在区域内再随机选取，即是结果。

代码实现

class Solution {
public:
    vector<vector<int>> recs;   // 保存区间
    vector<long long> t;    // 前缀和
    Solution(vector<vector<int>>& rects) {
        recs=rects;
        int n = rects.size();
        t.resize(n+1);
        t[0]=0;
        for(int i=0;i<n;i++){
            t[i+1]=t[i]+(rects[i][2]-rects[i][0]+1) * (rects[i][3]-rects[i][1]+1);
            //cout<<t[i+1]<<endl;
        }
    }
    vector<int> pick() {
        int n = recs.size();
        int ans=rand()%t[n];    // [0,m)的随机数
        //return {ans};
        int l=0;
        int r = n;
        while(l<r){     // 找到矩形的index
            int m = (r+l)/2;
            if(t[m]>ans) r=m;
            else l=m+1;
        }
        int x1 = recs[l-1][0];
        int y1 = recs[l-1][1];
        int x2 = recs[l-1][2];
        int y2 = recs[l-1][3];
        int xr = rand() %(x2-x1+1)+x1;      // 在矩形内随机x
        int yr = rand() %(y2-y1+1)+y1;      // 在矩形内随机y
        return {xr,yr};
    }
};

小结

1. 如何模拟具有不同概率的古典概型？

2. 为什么要使用前缀和?

3. 二分模板写法?