题目:56. 合并区间
题目描述:
给你一个二维数组,类似于[[1, 3], [2, 6], [6,10], [15,18]]
,其中每一个元素表示一个区间,区间0
下标表示区间左边界,1
下标表示区间右边界。题目要求返回合并区间之后的数组,如何合并呢?上一个区间的右边界大于等于下一个区间的左边界,就可以合并。例如[1, 3], [2, 6], [6,10]
这三个区间就可以合并,合并为[1, 10]
。最终返回所有合并之后的数组,例如上面的数组,最终返回[[1,10], [15,18]]
即可。
思路:
首先,二维数组是无序的,那么在遍历过程中就不能确定,当前遍历的区间和下一个区间能不能合并。所以要先将二维数组排序,按照区间的左边界进行升序。这样能合并的区间,下标一定都相邻。排序之后,就开始遍历,遍历到一个区间,判断能否合并,其实就是判断上一个区间的右边界大于等于下一个区间的左边界,如果满足合并,那么就可以更新一下最大值和区间下标。找到最后一个满足合并条件的区间,说明下一区间是下一个合并区间的开头。这样不断遍历,遍历完所有的二维数组,就得到最终合并区间之后的数组啦!
步骤:
1、将二维数组按照区间的左边界进行升序。
2、遍历排序后的二维数组,判断是否满足合并条件,满足则更新最大值和下标,将下标不断往后推。找到最后一个满足合并条件的区间,将最终记录的最大值和最小值存进集合。
3、将集合转化为数组返回。
代码:
public int[][] merge(int[][] intervals) {
// 以数组左区间进行排序,排序之后,能合并的区间,下标一定都相邻
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
// 记录最小值 和 目前已经合并的最大值
int min = intervals[i][0];
int max = intervals[i][1];
// 如果下一区间不越界 且 目前已经合并的最大值 >= 下一区间的左区间,说明需要继续合并
while (i + 1 < intervals.length && max >= intervals[i + 1][0]) {
// 更新已经合并的最大值
max = Math.max(max, intervals[i + 1][1]);
i++;
}
// 合并已经结束,最大值最小值都找到了
int[] arr = new int[2];
arr[0] = min;
arr[1] = max;
list.add(arr);
}
// 将 list 转化为 数组
int[][] ans = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) {
ans[i][0] = list.get(i)[0];
ans[i][1] = list.get(i)[1];
}
return ans;
}
标签:int,list,合并,HOT,intervals,数组,区间,100,LeetCode
From: https://www.cnblogs.com/yuhang-wiki/p/16988810.html