力扣_56之合并区间

发表于 分类于 评论数： 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 11 分钟

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例

1、

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

2、

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路

从题目描述，这个题就是把给定的数组，如有重叠就组合到一起，直到所有的数组都无法重叠，然后输出所有的数组。这个题，常规的做法就是将每个数组先按第一个元素排序，然后将根据数组的第二个元素拿出来和后一个数组进行比较，根据结果来进行是否合并或者保留。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
   		//先对二维数组中的一维数组进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        //在判断merged中的数组的第二个元素和当前遍历到的数组的两个元素进行比较，然后再判断如何添加
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

image-20211212205935591

我的思路是：

1、创建一个长度为n的数组box，n的值为给定的二维数组的数字的最大值。

2、然后遍历给定的数组，根据每一个一维数组元素，将其设为遍历box的起点和终点，并且把中间值设为1，起点设为1，终点设为2。（也可以设为其他值）

3、遍历所有的一维数组后，此时的box数组，将相当于，把所有覆盖的区间都设定了值。

4、再次遍历一维数组，把box中所有已经设定的值得区间的起点和终点记录下来即可。

代码实现：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public int[][] merge1(int[][] intervals) {
		int max=0;
   
    	//获取数组中的最大值
		for(int[] interval:intervals){
			max= Math.max(max, interval[1]);
		}
		int[] ints=new int[max+1];
    	//遍历给定数组，相当于把所有区间数在ints数组进行标记
		for(int[] interval:intervals){
			for(int i=interval[0];i<interval[1];i++){
				ints[i]=1;
			}
			ints[interval[1]]=ints[interval[1]]==1?1:2;
		}

    	//用两个栈来存结果的一维数组的左元素和右元素
		Stack<Integer> left=new Stack<>();
		Stack<Integer> right=new Stack<>();
		for(int i=0;i<ints.length;i++){
            //判断特殊情况
			if(i==0&&ints[i]==2){
				left.push(i);
				right.push(i);
				continue;
			}
			if(i==0&&ints[i]==1){
				left.push(i);
				continue;
			}
			if(ints[i]==1&&ints[i-1]==0){
				left.push(i);
				continue;
			}
			if(ints[i]==1&&ints[i-1]==2){
				left.push(i);
				continue;
			}

			if(ints[i]==2&&ints[i-1]==0){
				left.push(i);
				right.push(i);
				continue;
			}

			if(ints[i]==2&&ints[i-1]==2){
				left.push(i);
				right.push(i);
				continue;
			}
			if(ints[i]==2&&ints[i-1]==1){
				right.push(i);
				continue;
			}
			if(i==ints.length-1&&ints[i]==2){
				right.push(i);
			}
		}
		int leng=right.size();
		int[][] result=new int[leng][2];
    	//处理返回结果，从左栈和右栈分别取出左元素和右元素分别作为一维数组的第一个元素和第二个元素
		for(int i=0;i<result.length;i++){
            //pop元素可以从栈顶拿除元素，并删除栈中的元素
			result[i][0]=left.pop();
			result[i][1]=right.pop();
		}
		return result;
	}

image-20211212205705100

看这两种思路的时间可能第二种的时间更短（第一种的方法主要浪费在排序上了），但第二种思路不太好想，而且特殊情况需要考虑完全，才能通过，所以大家可以根据实际情况来选择合适的方法解题。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals