[toc]
1.题目描述
给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
https://leetcode-cn.com/problems/merge-intervals/
2.解题思路
对于此题，考虑到区间的比较，那么最容易想到的就是将区间从小到大的顺序进行排序。滞后再两两比较就会容易很多，但是由于输入和输出都是二维数组，那么肯定需要一个额外的结果集来存储输出结果或者使用Arrays.copyOf方法。
2.1 使用排序
需要注意的是二维数组的排序方法，如果要使用Arrays.sort();则需要自己实现一个比较方法。之后将发生比较的结果存储在另外一个数组中。完整解析如下：
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(v1,v2)-> v1[0]-v2[0]);
int res[][] = new int[intervals.length][2];
int index = -1;
for(int[] interval : intervals){
if(index== -1 || interval[0] > res[index][1]){
res[++index] = interval;
}else {
res[index][1] = Math.max(res[index][1],interval[1]);
}
}
return Arrays.copyOf(res,index+1);
}
在排序之后，申明了一个res数组来存储每次比较的结果，同时将使用index记录 res中添加元素的次数。最后采用Arrays.copyOf方法。
此算法由于开始进行了排序，后续又再次copy了结果，无论是时间还是空间都不是最优的算法。
image.png
2.1 不使用排序
如果不使用排序，那么用两次比较的话，只能将被合并进去的区间设置为null，之后再用另外一个数组将非空的元素copy出来。那么我们可以考虑双层for循环，由于外层的i只会进行一次比较，那么当出现合并情况之后，将i指向的元素设置为null，之后将j指向的元素合并，还可以再次进行比较。具体算法如下：
public int[][] merge(int[][] intervals) {
if(intervals == null || intervals.length <= 1){
return intervals;
}
int count = 0;
//循环比较，用i指向被合并的区间，j指向合并后的区间，入果存在合并，则i为null，并记录合并发生的次数count
for(int i=0;i<intervals.length;i++){
for(int j=i+1;j<intervals.length;j++){
if(intervals[i][0]<=intervals[j][1]&&intervals[i][1]>=intervals[j][0]){
intervals[j][0] = Math.min(intervals[i][0],intervals[j][0]);
intervals[j][1] = Math.max(intervals[i][1],intervals[j][1]);
intervals[i] = null;
count ++;
break;
}
}
}
//复制结果集
int index = 0;
int[][] res = new int[intervals.length - count][2];
for(int i=0;i<intervals.length;i++){
if(intervals[i] != null){
res[index][0] = intervals[i][0];
res[index][1] = intervals[i][1];
index++;
}
}
return res;
}
虽然代码量比第一种方法多了很多，但是时间和空间的效率要高很多。看来使用排序之后再合并并不是一个好办法。
image.png
网友评论