Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

合并区间

Posted on Edited on In , ,
Symbols count in article: 2.8k Reading time ≈ 3 mins.

来自Leetcode第56题合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

排序

思路很简单，就是先将数组按照左边有序的顺序排列，一开始我自己还写了一个排序算法，运行时间大大增加，傻了，放着现成的不用

题解里采用了lamda表达式的方法，而且list和数组的转换很赞

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[][] merge(int[][] intervals) {
    List<int []> ans = new ArrayList<>();
    if(intervals == null || intervals.length == 0)
        return ans.toArray(new int[0][]);
    //Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
    // 根据二维数组第一个数字大小按每一行整体排序
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] ints, int[] t1) {
            return ints[0] - t1[0] ;
        }
    });
    int i = 0 ;
    while(i < intervals.length){
        int left = intervals[i][0];
        int right = intervals[i][1];
        //合并区间，判断right 是否比下一个区间的左值大
        while(i < intervals.length  && right>= intervals[i][0]){
            //重新对right赋值
            right = Math.max(right,intervals[i][1]);
i++；
        }
        ans.add(new int[] {left,right});
    }
    return ans.toArray(new int [0][]);
}

自己的原代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int[][] merge(int[][] intervals) {
    List<int []> ans = new ArrayList<>();
    if(intervals == null || intervals.length == 0)
        return ans.toArray(new int[0][]);
    sort(intervals);
    int i = 0 ;
    while(i < intervals.length){
        int left = intervals[i][0];
        int right = intervals[i][1];
        //合并区间，判断right 是否比下一个区间的左值大
        while(i < intervals.length  && right>= intervals[i][0]){
            //重新对right赋值
            right = Math.max(right,intervals[i][1]);
            i++;
        }
        ans.add(new int[] {left,right});
    }
    return ans.toArray(new int [0][]);
}

public void sort (int [][] intervals){
    int len = intervals.length;
    for(int i = 0 ; i < len ; i++)
        for(int j = i + 1 ; j < len ; j++){
            if(intervals[i][0] > intervals[j][0]){
                int temp1 = intervals[i][0];
                intervals[i][0] = intervals[j][0];
                intervals[j][0] = temp1;
                int temp2 = intervals[i][1];
                intervals[i][1] = intervals[j][1];
                intervals[j][1] = temp2;
            }
        }
}

执行时间1ms

在看用时分布时，看了一下用时为1ms的代码，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length<=1){
            return intervals;
        }
        //计数用来表示合并了多少个区间
        int mergeCount = 0;
        for(int i = 0;i<intervals.length;i++){
            for(int j = i+1;j<intervals.length;j++){
                if(intervals[i][1]>=intervals[j][0] && intervals[i][0]<=intervals[j][1]){
                    //开始合并区间的讨论
                    if(intervals[i][1]>intervals[j][1]){
                        //(i,0) < (j,0) < (j,1) < (i,1)
                        intervals[j][1] = intervals[i][1];
                    }
                    if(intervals[i][0]<intervals[j][0]){
                        //(i,0) < (i,1) < (j,0) < (j,1)
                        intervals[j][0] = intervals[i][0];
                    }
                    intervals[i] = null;
                    mergeCount++;
                    break;
                }
            }
        }
        int[][] result = new int[intervals.length-mergeCount][];
        for(int i = 0,j = 0;j<intervals.length;j++){
            if(intervals[j] != null){
                result[i++] =intervals[j];
            }
        }
        return result;
    }
}