美文网首页
刷题-leetcode:436. 寻找右区间

刷题-leetcode:436. 寻找右区间

作者: marksman_e902 | 来源:发表于2020-02-13 17:58 被阅读0次

    题目地址:https://leetcode-cn.com/problems/find-right-interval/

    给定一组区间,对于每一个区间 i,检查是否存在一个区间 j,它的起始点大于或等于区间 i 的终点,这可以称为 j 在 i 的“右侧”。

    对于任何区间,你需要存储的满足条件的区间 j 的最小索引,这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在,则将区间 i 存储为 -1。最后,你需要输出一个值为存储的区间值的数组。

    注意:

    你可以假设区间的终点总是大于它的起始点。
    你可以假定这些区间都不具有相同的起始点。
    示例 1:

    输入: [ [1,2] ]
    输出: [-1]

    解释:集合中只有一个区间,所以输出-1。
    示例 2:

    输入: [ [3,4], [2,3], [1,2] ]
    输出: [-1, 0, 1]

    解释:对于[3,4],没有满足条件的“右侧”区间。
    对于[2,3],区间[3,4]具有最小的“右”起点;
    对于[1,2],区间[2,3]具有最小的“右”起点。
    示例 3:

    输入: [ [1,4], [2,3], [3,4] ]
    输出: [-1, 2, -1]

    解释:对于区间[1,4]和[3,4],没有满足条件的“右侧”区间。
    对于[2,3],区间[3,4]有最小的“右”起点。

    编程思路

    此题可以硬解,先遍历所有区间尾,对于每尾再遍历一次所有的头,找出最小的即可。我选择麻烦一点,先对区间们依据区间首进行升序排序,然后再从头依次遍历区间尾,从该区间起向后查找。

    • 二路归并排序
      对区间的排序采用二路归并排序。归并排序使用分治思想,稳定,最好最坏平均时间复杂度都是O(nlog2n)。同样时间复杂度的排序中,快速排序不稳定,且当元素顺序和逆序时出现最坏情况O(n²),堆排序不稳定。归并排序消耗内存O(n)。
      归并排序
      下面是归并排序过程,核心就是比较左右指针内容的大小,画画板做的gif将就着看吧。
      归并过程.gif
    • 折半查找
      区间排序完成后,起点已经是升序,接下来只需对所有区间尾依次进行处理,在其他区间找出比其大得最少或者值相等的一个起点。我们只需要对其后的区间的头进行查找即可,由于区间起点升序,因此采用二分查找法快些。
      例如对{2,5,7,17,18,56}进行折半查找,查找的路径相当于一个平衡的二叉排序树,查找成功也好,失败也好,最多也就比较树高次,是O(log2n)数量级。
      image.png

    代码

    class Solution {
    public:
        vector<int> findRightInterval(vector<vector<int>>& intervals) {
            int size=intervals.size();
            vector<int> indexes;
            vector<int> results;
            for(int k=0;k<size;k++){
                indexes.push_back(k);
                results.push_back(k);
            }
            mergeSort(intervals,indexes,0,size-1);
            //binary search
            for(int k=0;k<size;k++){
                int target=intervals[indexes[k]][1];
                int low=k+1,high=size-1,mid;
                int result=-1;
                while(low<=high){
                     mid=(low+high)/2;
                    if(target==intervals[indexes[mid]][0]){//found
                        result=indexes[mid];
                        break;
                    }
                    else if(target<intervals[indexes[mid]][0]){
                        result=indexes[mid];
                        high=mid-1;
                    }
                    else if(target>intervals[indexes[mid]][0]){
                        low=mid+1;
                    }
                }
                results[indexes[k]]=result;
            }
            return results;
        }
        /*
        custom merge sort,modified units' index will be stored in inputIndex
        */
        void mergeSort(vector<vector<int>>& inputVec,vector<int> &inputIndex,int low,int high){
            if(low<high){
                int mid=(low+high)/2;
                mergeSort(inputVec,inputIndex,low,mid);//left part sort
                mergeSort(inputVec,inputIndex,mid+1,high);//right part sort
                innerMerge(inputVec,inputIndex,low,mid,high);//both left and right already sorted,now merge them into one piece.
            }
        }
        /*
        merge low ~ mid and mid+1 ~ high into one piece
        */
        void innerMerge(vector<vector<int>>& inputVec,vector<int> &inputIndex,int low,int mid,int high){
            int i,j,k;
            auto indexCopy=inputIndex;
            printf("%d ",low);
            for(i=low,j=mid+1,k=low;i<=mid&&j<=high;k++){//caution:k=low
                if(inputVec[indexCopy[i]][0]<inputVec[indexCopy[j]][0]){//left<right
                    inputIndex[k]=indexCopy[i++];
                    
                }
                else {//left>right
                    inputIndex[k]=indexCopy[j++];
                }
            }
            
            while(i<=mid){
                inputIndex[k++]=indexCopy[i++];
                
            }
            while(j<=high){
                inputIndex[k++]=indexCopy[j++];
            }
        }
    };
    

    性能:

    都不好意思贴出来了


    image.png

    相关文章

      网友评论

          本文标题:刷题-leetcode:436. 寻找右区间

          本文链接:https://www.haomeiwen.com/subject/qipkfhtx.html