436. 寻找右区间--LeetCode

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/find-right-interval

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目大意是这样的

	数组中的元素由一个区间组成(包含一个左端点和右端点),左端点一定是唯一的

	找到每个元素的右区间

	举个例子

		假设区间A为[1,2],那么区间A的右区间最好就是[2,3]

		也就是说区间A右区间的左端点是大于等于区间A右端点的最小数

二分思路



从暴力算法上看，开销最大的部分就是枚举右区间

如果事先记录数组intervals的左端点并排序，那么右区间就可以二分(有序就可以二分)

代码如下



class Solution {

public:

    vector<int> findRightInterval(vector<vector<int>>& intervals) {

        vector<int> res;

        // intervals的长度为1时要做特判

        if(intervals.size()==1){

            res.push_back(-1);

            return res;

        }

        // 记录intervals中每个区间的左端点和该端点在哪个区间

        vector<pair<int,int>> tmp;

        for(int i=0;i<intervals.size();i++)

            tmp.push_back({intervals[i][0],i});

        // 将这些端点排序

        sort(tmp.begin(),tmp.end());

        for(int i=0;i<intervals.size();i++){

            int l=0,r=tmp.size()-1,mid;

            // 二分寻找对应的左端点

            while(l<r){

                mid = (l+r)/2;

                if(tmp[mid].first>=intervals[i][1])r=mid;

                else l=mid+1;

            }

            // 如果找到的左端点小于区间i的右端点就记录左端点所在区间

            // 否则记为-1 表示区间i没有右区间

            if(tmp[l].first>=intervals[i][1])res.push_back(tmp[l].second);

            else res.push_back(-1);

        }

        return res;

    }

};

巴特西

436. 寻找右区间--LeetCode_二分

二分思路

代码如下

最新文章

热门文章