LeetCode刷题之HOT100之合并区间

雨下了一整天，中午早早就回去吃饭拿快递了，今天拿了很多快递。我的书回来啦哈哈，还有好多零食，爽歪歪啊，放在下面了，然后准备开始做题啦！

图一：左一是xh送我的，非常精彩（其他都是618购入）只买了陀爷和小波的，白夜行是朋友极力推荐购入
下次购书就不知道是啥时候了，毕竟现在任务落在我们身上，很难挤出时间来看看。Anyway，随性些，做题吧！

1、题目描述

2、逻辑分析

题目要求很清晰。我的大致思路是：遍历每个数组，将 i + 1个数组的第一个元素a与第 i 个数组的第二个元素b进行比较，如果a < b , 那么这两个数组满足要求，需要合并。如 [1,3] , [2,6]。2 < 3,亟需合并。是的，我写不出来。看了题解发现我想的太easy，很多情况未考虑。题解思路：

1. 先排序，将整个数组以第一个元素进行排序。
2. 遍历区间，如果结果数组是空的，或者当前区间的起始位置 >
   结果数组中最后区间的终止位置，则不合并，直接将当前区间加入结果数组。反之将当前区间合并至结果数组的最后区间。

3、代码演示

public int[][] merge(int[][] intervals) {
        // 第一步：根据区间的起始值对数组进行排序  
        // 使用lambda表达式定义排序规则，按照每个区间的第一个元素（即起始值）进行升序排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 第二步：初始化结果数组，大小与原始区间数组相同（但可能不完全使用）
        int [][] res = new int[intervals.length][2];
        // index用于跟踪结果数组中当前已使用的最后一个位置
        int index = -1;
        // 第三步：遍历排序后的区间数组
        for(int [] interval : intervals){
            // 如果结果数组为空，或者当前区间的起始值大于结果数组中最后一个区间的结束值  
            // 则说明当前区间与前一个区间没有重叠，可以直接添加到结果数组中
            if(index == -1 || interval[0] > res[index][1]){
                // 注意这里++index是先使用index的值，再自增
                res[++index] = interval;
            }else{
                // 如果当前区间与前一个区间有重叠  
                // 则更新结果数组中最后一个区间的结束值为当前区间和前一个区间的结束值中的较大者  
                // 这样可以确保合并后的区间包含所有重叠的部分  
                res[index][1] = Math.max(res[index][1], interval[1]);
            }
        }
        // 第四步：返回合并后的区间数组  
        // 因为结果数组可能并没有完全使用，所以需要复制一个只包含有效区间的新数组  
        // Arrays.copyOf方法用于创建一个新数组，并复制指定长度的元素到新数组中
        return Arrays.copyOf(res, index + 1);// index + 1表示有效区间的数量
    }

这注释解释的较明了，一看就会，一做就废，还在新手期，加油吧！hx。

4、复杂度分析

时间复杂度：$O(n\log n)$。其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 $O(n\log n)$。
空间复杂度：$O(\log n)$。其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。$O(\log n)$ 即为排序所需要的空间复杂度。

over，拜拜~