☆打卡算法☆LeetCode 56、合并区间 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个数组表示若干个区间的集合，请你合并所有重叠的区间，返回一个不重叠的区间数组，该数组需恰好覆盖输入的所有区间。”

题目链接：

来源：力扣（LeetCode）

链接：56. 合并区间 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

以数组 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、思路分析

这个题的关键在于对于二维数组排序的应用，比如说按照区间的最左边开始，在排完序的数组中，合并的区间是连续的。

首先将列表中的区间按照左端点升序排序，然后将第一个区间加入到苏中，然后按顺序加入剩余的区间。

再加入剩余的区间的时候，要考虑，如果当前区间的左端点在数组中最后一个区间的右端点之后，那么他们不会重合，可以将这个区间加入数组的末尾。

否则，就是重合了，将当前区间的右端点更新数组中最后一个区间的右端点，重置两者的较大值。

2、代码实现

代码参考：

public class Solution {
    public int[][] Merge(int[][] intervals) {
        //排序数组
        Array.Sort(intervals, (x, y) => x[0].CompareTo(y[0]));
        //初始化变量
        List<int[]> ans = new List<int[]>();
        bool add;
        ans.Add(intervals[0]);
        //添加元素
        for (int i = 1; i < intervals.Length; i++)
        {
            add = true;
            //遍历已有区间
            foreach (int[] item in ans)
            {
                if (intervals[i][0]>item[1]||intervals[i][1]<item[0])
                {
                    continue;
                }
                item[0] = Math.Min(item[0], intervals[i][0]);
                item[1] = Math.Max(item[1], intervals[i][1]);
                add = false;
            }
            if (add) ans.Add(intervals[i]);
        }
        return ans.ToArray();
    }
}

3、时间复杂度

时间复杂度 ： O(n log n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(log n)

只需要常数级别的空间存放变量。

三、总结

这道题要关键在于数组的排序，数组的排序需要找到左节点和右节点，最终形成一个数组。

所以，要遍历所有的数组，找到最小的值放到最左边，最大的值放到最右边。

最终得到想要的答案。