LeetCode/统计包含每个点的矩形数目

929code / 2023-05-18 / 原文

所以矩形左下角为（0,0），右上角为（x,y）
给你一个二维整数数组 rectangles 和二维整数数组 points
求每个点占据的矩形数目

1. 暴力

遍历点然后遍历矩形

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
            int n = points.size();
            vector<int> res(n);
            for(int i=0;i<n;i++){//遍历每一个点
                int count = 0;
                int x = points[i][0];
                int y = points[i][1];
                for(auto&rec:rectangles)
                    if(x<=rec[0]&&y<=rec[1]) count++;
                res[i] = count;
            }
            return res;
    }
};

2. 优化

思考如何让当前点迅速找到占据多少个矩形。。。必然要先对矩形数据进行预处理
注意到矩形高度范围很小，可以将矩形按高度分类，然后按长度升序排列
这样判断点的时候，只需判断更高的矩形，同时可以采用二分查找满足条件的宽度下标，从而快速求出满足宽度条件的矩形

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
            int n = points.size();
            vector<int> res(n);
            //因为高度范围小，先按长度排序
            sort(rectangles.begin(),rectangles.end());//按升序排
            vector<vector<int>> dp(101);
            for(auto&rec:rectangles)
                dp[rec[1]].push_back(rec[0]); //把相同高度的按宽度升序放到一起

            for(int i=0;i<n;i++){//遍历每一个点
                int count = 0;
                int x = points[i][0];
                int y = points[i][1];
                for(int j=y;j<=100;j++){//遍历所有更高的高度
                    if(dp[j].size()==0) continue;//当前高度没有矩形
                    auto index = lower_bound(dp[j].begin(),dp[j].end(),x);//找大于长度的下标
                    if(index!=dp[j].end()) res[i]+= dp[j].size()-(index-dp[j].begin());
                }
            }
            return res;
    }
};