算法题--合并二维数组

> 华为OD招聘一面

### 算法题目：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 ：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

注意：数组intervals 并不一定是有序的。

### 思路：

intervals 数组是一个二维数组，里面的每个一维数组表示一个区间。既然是区间，那一定是{小, 大}，否则就不是区间了。由于原数组不一定是有序的，我们要操作的时候应该先对其排序，这样后面好操作。怎么排序呢？按照每个数组的第一位从小到大排序，比如：

排序前 intervals = [[8,10],[1,3],[15,18],[2,6]]，我们要排成这样：

排序后 intervals = [[1,3],[2,6],[8,10],[15,18]]。这样它就是呈趋势递增的。

首先第一个数组的第1位肯定是所有数字中最小的。然后第二位是第一个区间的右端，这个区间有没有和第二个区间重叠的呢？

1、我们应该先判断是否“交界”，然后再判断是否“有重叠”，还有一种情况是“包含”。

无交界：1,5  6,7。如果无交界，那么这两个数组就是两个区间

有重叠：1,5  3,6。如果有重叠，那么这我们要的区间应该是：左端是最小，右端是最大的。即1,6

全包含：1,5  2,3。如果全包含，那么我们应该舍弃第二个数组，因为她的区间已经存在于第一个数组的区间了。

2、假设前两个数组是1,5  6,7 ，我们合并前两个数组的区间，得到的结果就还是1,5  6,7。接下来呢？接下来该拿6,7和下一个数组比了，因为后面的数组的第一位一定比6大。

假设前两个数组是1,5  3,6 ，我们合并前两个数组的区间，得到的结果就是1,6。接下来呢？接下来该拿1,6和下一个数组比了。

所以，我们在进行完1的比较后，能够得出一个暂时的结果数组集合。需要拿这个集合中，最靠后的，和未比较的数组比较。

依次循环上述步骤，最终可得到结果集。

### 代码：

```java
package com.example.demo.core.Leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: HanXu
 * on 2022/2/16
 * Class description: 合并二维数组
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * 示例 ：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
 */
public class MergeTwoDimensionArray {
    public static void main(String[] args) {
        //int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        //int[][] intervals = {{1, 3}, {2, 4}, {3, 10}, {6, 8}};
        int[][] intervals = {{3, 5}, {2, 4}, {6, 10}, {1, 5}};
        int[][] resultArr = mergeArr(intervals);
        for (int i = 0; i < resultArr.length; i++) {
            System.out.println(Arrays.toString(resultArr[i]));
        }
    }

public static int[][] mergeArr(int[][] intervals) {
        //特殊情况处理
        if (intervals.length < 2) {
            return intervals;
        }

//先排序，按照第一位升序排序
        Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));
        //使用集合储存结果
        List<int[]> resultList = new ArrayList<>();
        //第一个数组的第1位是最小的，先加入
        resultList.add(intervals[0]);

//从第1位开始循环遍历数组
        for (int i = 1; i < intervals.length; i++) {
            //取结果集中的最后一个数组
            int[] ints = resultList.get(resultList.size() - 1);
            //如果第2位 < 当前数组的第1位，则不在前者数组的范围内，当前数组是新的范围，需要加入结果集中  1,3  4,5  后者是新范围
            if (ints[1] < intervals[i][0]) {
                resultList.add(intervals[i]);
            } else if (ints[1] < intervals[i][1]) {
                //上面那个if每过说明第2位 大于等于 当前数组的第1位。那么看她究竟有多大：
                //如果第2位 < 当前数组的第2位（没大过当前数组的第二位），那么表示和当前数组有重叠部分，需要取当前数组的第2位作为区间的右端  1,5  3,6 -> 1,6
                ints[1] = intervals[i][1];
                //这里直接改变ints[1]的值就行，因为是数组，会影响对应内存空间中的值。也就是说改变会在所有引用中（resultList）都生效
            }//最后一种情况就是第2位 >= 当前数组的第2位，那么说明当前数组完全在ints数组的区间内，则丢弃当前数组  1,6  2,4 -> 1,6 (丢弃2,3)
        }

//返回结果集，注意设置数组两个维度的容量
        return resultList.toArray(new int[resultList.size()][2]);
    }
}
```

算法题--合并二维数组

文章目录

发表评论