【hot100】056合并区间

一、思路

此题的重点是排序，因为判定重合的条件是区间1的右边界大于区间2的左边界，所以通过左边界进行排序就可以通过一次遍历把重合的的区间全部合并

二、记忆

1.重写Arrays.sort()方法比较函数

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

此处重写了方法中的compare函数，此处@Override可以省略，编译器会根据函数名自动判断，但是加上会提高可读性

 2.二维数组

在 Java 中，二维数组实际上是“数组的数组”，即每个二维数组的元素本身又是一个一维数组。这种结构常常被理解为行和列的形式，但需要注意以下几点：

3.ArrayList和数组相互转化

ArrayList<int[]> merge = new ArrayList<>();

merge.add(intervals[i]);

merge.get(merge.size()-1)[1] ;  //获取到的是地址，可以直接进行赋值

merge.toArray(new int[merge.size()][])

三、代码

public int[][] merge(int[][] intervals){
        if(intervals.length==0) return new int[0][2];
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        ArrayList<int[]> merge = new ArrayList<>();
        merge.add(intervals[0]);
        for (int i =1;i<intervals.length;++i){
            if (merge.get(merge.size() - 1)[1]<intervals[i][0]){//融合区间的右边界小于当前边界左边界，说明并没有相交
                merge.add(intervals[i]);
            }else {//有相交
                merge.get(merge.size()-1)[1] = Math.max(merge.get(merge.size()-1)[1],intervals[i][1]);
                //注意此行的语法，merge.get(merge.size()-1)[1]获取到的是地址，可以直接进行赋值
                // 虽然merge的右边界大于当前边界左边界，但是并不一定小于当前边界右边界，即可能完全包含当前边界，所以还需判断
            }
        }
        return merge.toArray(new int[merge.size()][]);
    }