LeetCode hot 100 每日一题(10)——56. 合并区间
这是一道难度为中等的题目,我们来看看题目描述:
以数组
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 <= intervals.length <= 1 0 4 10^4 104
- intervals[i].length == 2
- 0 <= s t a r t i start_i starti <= endi <= 1 0 4 10^4 104
说人话解释:
求重叠的区间并集,然后返回所有的并集
题解
class Solution {
public int[][] merge(int[][] intervals) {
// 创建LinkedList存储合并后的空间,方便在尾部插入和删除元素
LinkedList<int[]> res = new LinkedList<>();
// 按照区间的起点进行排序
Arrays.sort(intervals, (a, b) -> {return a[0] - b[0];});
//先将第一个区间加入结果列表
res.add(intervals[0]);
//遍历剩下的所有区间,所以从i = 1开始
for(int i = 1; i < intervals.length; i++){
int[] curr = intervals[i]; // 当前遍历的区间,是列表
int[] last = res.getLast(); // 获取结果列表中的最后一个区间
// 如果当前区间起点小于或等于上一个区间的终点,说明区间有重叠
if(curr[0] <= last[1]){
// 更新结果列表中的最后一个区间的终点
last[1] = Math.max(last[1], curr[1]);
}else{
// 如果没有重叠,直接将当前区间加入列表
res.add(curr);
}
}
//将LinkedList转换为二维数组返回
return res.toArray(new int[1][1]);
}
}
问题与解答
[NOTE] 问题1
Arrays.sort(intervals, (a, b) -> {return a[0] - b[0];});
中(a, b) -> {return a[0] - b[0];}
这是什么用法?
解答:
(a, b) -> {return a[0] - b[0];}
是 Lambda 表达式,用于 Java 8 及以上版本的简洁写法,相当于实现Comparator<int[]>
接口的compare
方法。
其作用是按照数组intervals
的第一个元素(即起点start_i
)进行升序排序。
等价于:Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { return a[0] - b[0]; } });
a[0] - b[0]
返回负数(a[0] < b[0]
),则a
排在b
前面;a[0] - b[0]
返回正数(a[0] > b[0]
),则b
排在a
前面;a[0] - b[0]
返回0
,则a
和b
位置不变(即视为相等)。
[NOTE] 问题2
int[] curr = intervals[i]; // 当前遍历的区间,是列表
int[] last = res.getLast(); // 获取结果列表中的最后一个区间
这里取出来的是列表还是数组?形如[i, j]的是列表还是数组?
curr[0]是当前区间的起点,curr[1]是当前区间的终点吗?
last[0]是结果列表中最后一个区间的起点,last[1]是结果列表中最后一个区间的终点吗?
解答:
取出的是数组,不是列表。这里curr
和last
都是int[]
类型的数组,表示一个区间[start, end]
。形如[i, j]
的数据结构是int[]
数组,而不是List
Java 里没有像 Python 那样的列表(list
),int[]
是固定大小的数组,而List<int[]>
则是存储多个int[]
的动态集合。
在 Java 中,数组(Array) 和 列表(List,通常指ArrayList
) 是两种常见的数据结构
- 数组(Array):大小是固定的,创建后不能更改长度。可以存储基本数据类型(如
int
、double
) 也可以存储对象类型。- 列表(List):大小是动态的,可以根据需求增删元素。只能存储对象类型(
ArrayList<int>
不合法,必须使用ArrayList<Integer>
)。
curr[0]
和curr[1]
代表当前区间的起点和终点。
last[0]
和last[1]
代表res
结果列表中最后一个区间的起点和终点
[NOTE] 问题3
res.toArray(new int[1][1]);
中的toArray用法是什么?
解答:
res.toArray(new int[0][0])
用于将LinkedList<int[]> res
转换为 二维数组int[][]
。
toArray()
方法作用:
toArray(new int[0][0])
方式可以将LinkedList<int[]>
直接转换为int[][]
数组。- 由于
res
是LinkedList<int[]>
,需要转换为int[][]
返回,因此toArray()
适用于数组转换。等价于:
int[][] result = new int[res.size()][2]; for (int i = 0; i < res.size(); i++) { result[i] = res.get(i); } return result;
为什么用
new int[0][0]
?
- 由于
toArray(T[] a)
需要传入一个 相同类型的数组,但不需要指定大小(JVM 会自动调整大小)。new int[0][0]
只是一个占位符,toArray
会创建合适大小的int[][]
并返回。
[NOTE] 问题4
LinkedList<int[]> res = new LinkedList<>();
创建的是什么数据结构?是双链表LinkedList吗?
解答:
是 双向链表LinkedList
,LinkedList<int[]>
代表一个 存储int[]
数组的双向链表。
LinkedList<int[]> res = new LinkedList<>();
LinkedList<>
是 Java 的 双向链表实现,允许快速插入和删除元素。- 这里
res
存储的是int[]
类型的数组,即每个元素都是形如[start, end]
的区间。- 为什么用
LinkedList
而不是ArrayList
?
LinkedList
的getLast()
方法可以快速获取最后一个元素。- 插入新区间的操作更快,因为
LinkedList
直接修改指针,而ArrayList
可能需要扩容和移动数据。