問題描述
以陣列 intervals 表示若干個區間的集合，其中單個區間為 intervals[i] = [starti, endi] ，請你合并所有重疊的區間，并回傳一個不重疊的區間陣列，該陣列需恰好覆寫輸入中的所有區間，
示例 1：
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2：
輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區間 [1,4] 和 [4,5] 可被視為重疊區間，
提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
解題思路
如果我們按照區間的左端點排序，那么在排完序的串列中，可以合并的區間一定是連續的，或者，我們可以考慮，如果不對區間的左端點進行排序，那么對于任何相鄰的兩個區間，我們有以下幾種關系
可以看到，兩個區間有5種關系，如果我們按照區間的左端點進行排序，那么只有3種關系
其實關系1和關系2可以合并為重疊關系，關系3則是不重疊關系，
這里區間集都是用二維陣列來表示的，那么問題來了，在Java中如何對二維陣列按照指定條件進行排序呢？
同樣是需要實作Comparator介面的compare方法，在Arrays.sort()函式中傳入一個比較器，比較器用匿名內部類實作
Java中對二維陣列按照條件進行排序的示例代碼如下：
public static void main(String[] args) {
// TODO Auto-generated method stub
int [][]matrix={{1,3},{6,8},{2,6},{4,7},{7,19},{12,18}};
Arrays.sort(matrix,new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
for(int i=0;i<matrix.length;i++){
System.out.println("x1="+matrix[i][0]+" x2="+matrix[i][1]);
}
}
我們用動態陣列 ArrayList集合lists來存盤最終的答案，
首先，我們將串列中的區間按照左端點升序排序，
隨后，掃描整個區間，掃描的程序中我們把所有可能有交集的區間進行合并，
我們每次需要維護一個當前的區間，并在回圈前，另待合并區間的第一個區間作為當前區間：
-
如果我們掃描時選中的區間的左端點在當前區間的右端點之后，那么它們不會重合，我們可以將當前區間添加到結果集合中，并更新當前區間為掃描時選中的區間；
-
否則，它們重合，我們需要比較當前區間的右端點值和掃描時選中的區間的右端點值，將當前區間的右端點值置為二者的較大值，
-
實作代碼
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals.length==0 ||intervals.length==1){
return intervals;
}
//對區間左端點進行排序
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int []o1,int []o2){
return o1[0]-o2[0];
}
});
//創建動態陣列用于保存最終結果集
List<int[]> lists=new ArrayList<int[]>();
int start=intervals[0][0],end=intervals[0][1];
int len=intervals.length;
for(int i=1;i<len;i++){
//當選中的區間左端點大于當前區間的右端點時，兩區間沒有交集
if(intervals[i][0]>end){
//把當前區間左右端點添加到結果集中
int []temp=new int[2];
temp[0]=start;
temp[1]=end;
lists.add(temp);
//更新當前區間左右端點
start=intervals[i][0];
end=intervals[i][1];
//當選中的區間左端點小于等于當前區間的右端點時，兩區間有交集
}else{
end=Math.max(intervals[i][1],end);
}
}
//最侄訓需要把當前區間的左右端點添加到結果集中
int []temp=new int[2];
temp[0]=start;
temp[1]=end;
lists.add(temp);
int reslen=lists.size();
int [][]res=new int[reslen][2];
//把動態陣列的結果集加入到二維陣列結果集中
for(int i=0;i<reslen;i++){
res[i][0]=lists.get(i)[0];
res[i][1]=lists.get(i)[1];
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/259721.html
標籤：java
上一篇：2021-02-13