力扣LeetCode56题：合并区间（Arrays.sort()方法的扩展使用）

一时失言乱红尘 2023-02-17 11:21 28阅读 0赞

题目：

> 给出一个区间的集合，请合并所有重叠的区间。  
>   
> 示例 1:  
> 输入: \[\[1,3\],\[2,6\],\[8,10\],\[15,18\]\]  
> 输出: \[\[1,6\],\[8,10\],\[15,18\]\]  
> 解释: 区间 \[1,3\] 和 \[2,6\] 重叠, 将它们合并为 \[1,6\].  
>   
> 示例 2:  
> 输入: \[\[1,4\],\[4,5\]\]  
> 输出: \[\[1,5\]\]  
> 解释: 区间 \[1,4\] 和 \[4,5\] 可被视为重叠区间。

#### 分析： ####

题目看起来还是挺简单的一个题目，就是要求并区间，数学里面我们都知道怎么做。

那如果对于示例 1 和示例 2 来说，当前一个区间的右端点 > 后一个的左端点， 就可以将这两个区间合并。

但是，示例的两个输入，**区间的左端点是有序的**，而实际输入可能是乱的。

所以这个问题就变成了，先要**对原来的输入进行按照区间左端点的排序**，再进行合并操作。

#### 相关知识 ####

那么体现在实现层面，就是对二维数组的 intervals\[x\]\[0\] 进行排序，之后再从头到尾遍历一遍，用 intervals\[x\]\[1\] 和 intervals\[y\]\[0\] 作比较。

（如果自己还是实现一个排序算法应该不是这个题目的重点？）  
调用 Arrays.sort 算法的扩展操作：

###### Arrays.sort()方法原则上只能对一维数组进行排序，但是这里需要对二维数组的某一列进行排序，就用到了这个函数的进阶 ######

###### 扩充 Comparator 接口，排序时将此接口的实现传递给 Collections.sort 方法或者Arrays.sort 方法进行排序。 ######

Arrays.sort()方法的源码分析可以参考这篇博客：

[浅谈Arrays.sort()原理][Arrays.sort]

尤其当集合中的对象**不支持自比较** 或者 **自比较的功能不能满足需求** 时可以使用它来进行指定，比如说在一些实际应用里面：有一个学生类，包含一些信息，名单出来之后想按照他们的其中一个属性 语文成绩 排序这样的情况。

这里我们想要对二维数组进行排序，并且要指定排序的是这个二维数组里面的啥东西，所以要利用这个接口实现类来进行指定。

具体的使用方法如下：

对于一个一维数组：

int[] a={
        1,2,3,4,5}

我们本来调用Arrays.sort()方法的时候可以这样

Arrays.sort(a);

就完全可以了，表示对a数组进行排序，因为他里面的元素世界可以进行排序，是基本类型。

如果数组a是这样呢：

int\[ \]\[ \] a= new int\[ \]\[ \]\{ \{1,3\},\{1,2\},\{4,5\},\{3,7\}\};

遇到这里的二维数组，这里面的**每个元素是一个数组对象**，没有实现Comparator接口，所以如果想要排序需要我们实现这个接口：

Arrays.sort(a,new Comparator<int[]>(){
        
        @Override
        public int compare(int[] a,int[] b){
        
            return a[0]-b[0];
        }
    });

这段代码的功能就是，对于a数组进行排序，实现了一个 Comparator 接口。

##### 在这里面，我们用 compare 方法规定，对于两个元素的比较（两个元素都是一维数组），a 和 b 数组，返回这两个数组第 0 个元素的比较结果。 #####

也就是对二维数组排序的时候，按照里面每一个元素（是一个一位数组）的第一列元素进行比较。

这样的写法也可以进行简化成 Lambda 表达式：（java 8 之后支持的新特性）

Arrays.sort(arr,(a,b)->a[0]-b[0]);

表达的是和上面复写compare方法一样的意思：对于a和b的比较，比较a\[0\]和b\[0\]。

#### 实现 ####

于是我们可以写出这道题目的代码：

1.  排序，按照第一列排序，得到区间的左端点有序的一组区间集合
2.  开始合并；
    
    1.  两个区间合并的条件是 前一个区间的右端点 大于等于 后一个区间的左端点 。
    2.  合并之后左端点为前一个区间的左端点；右端点为两个区间的右端点中较大的一个。（比如 \[1,4\]\[2,3\] ，合完之后左右端点都是第一个区间）
3.  合并完之后整个数组的内容是变少的，移动也不方便，因此将不需要的部分进行处理；
4.  将结果重新遍历放进一个新数组，作为答案返回。

class Solution {
        
        public int[][] merge(int[][] intervals) {
        
        	//首先让区间左端点有序
            Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
            
            int row=intervals.length;
            int row1=intervals.length;
            int i=0;
            while(i<row){
        
                int j=i+1;
                while(j<row&&intervals[j][0]<=intervals[i][1]){
        
                    
                    intervals[i][1]=intervals[j][1]>=intervals[i][1]?intervals[j][1]:intervals[i][1];
    
                    intervals[j][0]=Integer.MIN_VALUE;//为了方便被合并过的标记一下
                    intervals[j][1]=Integer.MIN_VALUE;
    
                    row1--;//记录答案的数组size，每合并一次就会少一个元素
    
                    j++;
                }
                i=j;//调到下一个没有被判断过的开始
            }
    
            //然后重新赋值返回答案
            int[][] ans=new int[row1][2];
    
            for(int j=0,k=0;j<row&&k<row1;j++){
        
                if(intervals[j][0]>Integer.MIN_VALUE){
        
                    ans[k][0]=intervals[j][0];
                    ans[k][1]=intervals[j][1];
                    k++;
                }
            }
            return ans;
        }
    }

[Arrays.sort]: https://blog.csdn.net/Duuuhs/article/details/89167231