LeetCode[56]合并区间-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode[56]合并区间。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

难度：Medium

题目：

以数组 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

重点！！！解题思路

第一步：

明确解题手段：使用排序算法是肯定的了，因为判断区间是否是交集或者包含关系，需要比较前一个数组的第二个值和后一个数组的第一个值之间的关系，想要不考虑其他情况就这样比较的话，我们需要先给整个二维数组排序，依据每个数组的第一个值进行排序。

第二步：

依据每个数组的第一个值进行排序后，就可以依次进行比较，判断数组中是交集还是包含关系了，具体代码如下

源码+讲解：

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });  //排序
        int[][] res=new int[intervals.length][2];  //结果数组
        int ind=-1;  //模拟数组真实的大小
        for (int[] interval : intervals) {
            if (ind==-1 || interval[0]>res[ind][1]){  //当是第一个数组或者此时数组第一个值大于前一个数组的第二个值，说明数组不相交，之间添加到结果数组就可以
                res[++ind]=interval;
            }else{  //要不然就是说明数组相交，那么相交的结果就改变前一个数组的第二个值就可以
                res[ind][1]=Math.max(interval[1],res[ind][1]);
            }
        }
        return Arrays.copyOf(res,ind+1);  //copyOf方法是将数组的真实大小拷贝到新的数组进行返回，因为如果有交集那么肯定少返回一个，那么数组对应的位置就会是空集，这个方法避免了空集的存在
    }
}

运行结果：

LeetCode[56]合并区间,算法刷题篇,快速排序（刷题篇）,# 算法杂谈系列：有趣的排序思想（刷题篇）,leetcode,算法,排序算法