leetcode 56合并区间 java

//先排序，将左区间小的放在前面，然后如果前一个的右区间大于下一个的左区间，则可以合并，分别用两个下标指向当前的大区间和将要考察的小区间

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length<=1)
            return intervals;
        quickSort(intervals,0,intervals.length-1);
        int j=0;
        for(int i=0;i<intervals.length;i++)
        {
            if(intervals[j][1]>=intervals[i][0])
            {
                intervals[j][1]=Math.max(intervals[j][1],intervals[i][1]);
            }
            else
            {
                j++;
                intervals[j][0]=intervals[i][0];
                intervals[j][1]=intervals[i][1];
            }
        }
        int[][] res = Arrays.copyOfRange(intervals, 0, j+1);
        return res;
    }
    public void quickSort(int[][] arr,int l,int r)
    {
        if(l>=r)
            return ;
        int p=partition(arr,l,r);       //执行partition操作将数组分成两份
        quickSort(arr,l,p-1);
        quickSort(arr,p+1,r);
    }
    public int partition(int[][] arr,int l,int r)
    {
        int v=arr[l][0];
        int i=l;        //[l-i]为左半部分初始为0，小于i的部分包括i
        for(int k=l+1;k<=r;k++)
        {
            if(arr[k][0]<v)
            {
                 swap(arr,k,i+1);
                 i++;
            }

        }
        swap(arr,l,i);
        return i;
    }
    public void swap(int[][] arr,int i,int j)
    {
        int temp=arr[i][0];
        arr[i][0]=arr[j][0];
        arr[j][0]=temp;
        int y=arr[i][1];
        arr[i][1]=arr[j][1];
        arr[j][1]=y;
    }
}

巴特西

leetcode 56合并区间 java

最新文章

热门文章