【算法训练-排序算法 三】【排序应用】合并区间

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【合并区间】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

合并区间【MID】

一道一直想要解决的高频题，用到了排序

题干

解题思路

如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的

我们用数组 merged 存储最终的答案。

• 首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
• 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
• 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

总体思路是左端点从小到大排列，每次比较只要比较新区间的左端点是否在已合并区间右端点之后就可以了，在之后则独立，在之前则重叠（而且由于左端点升序，在之前也是在之前已合并区间的中间，极端情况是和已排序区间左端点重叠）

代码实现

给出代码实现基本档案

基本数据结构：数组
辅助数据结构：无
算法：快速排序（分治算法）、二分查找
技巧：双指针

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类ArrayList
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // 1 先对集合进行排序
        intervals.sort(Comparator.comparingInt(interval -> interval.start));

        // 2 遍历顺序数组进行合并
        ArrayList<Interval> result = new ArrayList<Interval>();
        for (Interval interval : intervals) {
            // 2-1 获取当前区间左右端点和已合并区间右端点
            int leftPoint = interval.start;
            int rightPoint = interval.end;

            // 2-2 如果结果区间为空或者当前区间左端点大于已合并区间右端点，则当前区间作为独立子区间加入集合
            if (result.size() == 0 || leftPoint > result.get(result.size() - 1).end) {
                result.add(interval);
            } else {
            // 2-3 否则认为当前区间与已合并区间有重叠，只需更新合并区间右端点
                result.get(result.size() - 1).end =  Math.max(result.get(result.size() - 1).end, rightPoint);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

leetcode数组入参的处理方法：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    public int[][] merge(int[][] intervals) {
        // 1 先对数组进行排序
        Arrays.sort(intervals, Comparator.comparingInt(interval->interval[0]));

        // 2 遍历已排序数组，进行区间合并
        int[][] result = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {
            // 2-1 获取当前区间左右边界以及合并区间右边界
            int leftPoint = interval[0];
            int rightPoint = interval[1];

            // 2-2 如果已合并区间为空，或当前区间左端点大于已合并区间右端点，则不重叠
            if (idx == -1 || result[idx][1] < leftPoint) {
                idx++;
                result[idx] = interval;

            } else {
                // 2-3 反之则重叠，已两个区间较大值为新的右边界
                result[idx][1] = Math.max(result[idx][1], rightPoint);
            }
        }

        return Arrays.copyOf(result, idx + 1);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

复杂度分析

合并区间是一个常见的算法问题，通常用于合并具有重叠部分的区间，以简化问题或提供更清晰的表示。以下是关于合并区间问题的时间复杂度和空间复杂度的讨论：

时间复杂度：
时间复杂度是衡量算法性能的关键指标，它表示算法在输入规模增加时所需的运行时间。对于合并区间问题，一种常见的解决方法是首先将区间按照起始值进行排序，然后遍历这些区间并合并它们。

1. 排序：对区间按照起始值进行排序通常需要 O(n*log(n)) 的时间复杂度，其中 n 是区间的数量。

2. 遍历和合并：一旦区间排序完成，遍历区间并合并重叠的部分通常需要线性时间，即 O(n)。

因此，综合来看，合并区间的时间复杂度通常是 O(n*log(n))，其中 n 是区间的数量。这是由排序操作的时间复杂度主导的。

空间复杂度：
空间复杂度表示算法在执行过程中所需的额外内存空间。对于合并区间问题，空间复杂度通常取决于存储合并后的区间的数据结构。

1. 如果您在原始区间上就地修改，而不创建额外的数据结构，则空间复杂度是 O(1)，因为不需要额外的内存空间。

2. 如果您创建一个新的数据结构来存储合并后的区间，空间复杂度将取决于这个数据结构的大小。通常情况下，合并后的区间数目会少于或等于初始区间数目，因此空间复杂度也是 O(n)。

总结：合并区间问题的时间复杂度通常是 O(n*log(n))，空间复杂度可以是 O(1) 或 O(n)，具体取决于是否创建了新的数据结构来存储合并后的区间。

拓展知识：Arrays的用法

Arrays的一些用法拓展描述下

Arrays.copyOf(result, x)描述了什么

Arrays.copyOf(result, x) 是一个Java方法，它的含义是创建一个新数组，这个新数组的长度为 x，并且将原始数组 result 中的元素复制到新数组中。如果 x 小于原始数组的长度，那么新数组将截断，只包含原始数组中前 x 个元素。如果 x 大于原始数组的长度，新数组将在末尾用默认值填充，这个默认值取决于元素的数据类型，例如，数值类型默认是0，引用类型默认是null。

这个方法允许你在不改变原始数组的情况下创建一个具有不同长度的新数组，非常方便，特别是在需要调整数组大小时。例如：

int[] result = {1, 2, 3, 4, 5};
int x = 8; // 新数组的长度

int[] newArray = Arrays.copyOf(result, x);

// 新数组现在将会是 {1, 2, 3, 4, 5, 0, 0, 0}，长度为 8
1
2
3
4
5
6

在这个示例中，Arrays.copyOf 创建了一个长度为8的新数组，并将原始数组 result 中的元素复制到新数组中，多出的部分用0填充。

Arrays.sort(intervals, Comparator.comparingInt(interval->interval[0])) 描述下这个语句做了什么

这个语句使用了 Java 中的 Arrays.sort 方法来对一个二维数组 intervals 进行排序。排序是基于二维数组中每个子数组的第一个元素（interval[0]）的值来进行的，也就是按照子数组的起始值进行排序。

具体来说，这行代码的功能是：

1. intervals 是一个二维整数数组，通常用于表示区间（例如，区间的起始和结束值）。

2. Arrays.sort 是 Java 中用于对数组进行排序的方法。

3. Comparator.comparingInt(interval -> interval[0]) 是一个比较器，它告诉排序方法要按照每个子数组的第一个元素（interval[0]）的值进行升序排序。

所以，这个语句将根据 intervals 中每个子数组的第一个元素（起始值）来对二维数组进行排序，从小到大排列。排序后，intervals 数组中的子数组将按照它们的起始值从小到大的顺序排列。

这对于处理区间的问题非常有用，因为它可以将区间按照起始值进行排序，使得你可以更轻松地执行各种区间操作，比如合并重叠区间或查找包含某个点的区间等操作。