赞
踩
以数组 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] 可被视为重叠区间。
//时间复杂度为 O(nlogn) class Solution { public int[][] merge(int[][] intervals) { // 如果只有一个区间,直接返回 if(intervals.length == 1) return intervals; // 创建一个链表用于存储合并后的区间 LinkedList<int[]> result = new LinkedList<>(); // 按照区间的左端点进行排序 Arrays.sort(intervals, (a, b)-> { return a[0] - b[0]; }); // 初始化pre为第一个区间 int[] pre = intervals[0]; // 遍历排序后的区间数组 for(int i = 1; i < intervals.length; i++){ // 如果需要合并当前区间与pre if(pre[1] >= intervals[i][0]){ pre[1] = Math.max(pre[1], intervals[i][1]); // 合并后的右端点取二者的最大值 } else{ result.add(pre); // 否则,将pre加入结果 pre = intervals[i]; // 更新pre为当前区间 } } result.add(pre); // 将最后一个pre加入结果 // 转换为二维数组并返回 return result.toArray(new int[result.size()][]); } }
class Solution { public int[][] merge(int[][] intervals) { // 按照区间的左端点进行排序 Arrays.sort(intervals, (a, b)-> { return a[0] - b[0]; }); List<int[]> merged = new ArrayList<>(); for (int i = 0; i < intervals.length; i++) { // 如果 merged 数组为空或当前区间的左端点大于 merged 数组中最后一个区间的右端点 if (merged.isEmpty() || intervals[i][0] > merged.get(merged.size() - 1)[1]) { merged.add(intervals[i]); } else { // 更新 merged 数组中最后一个区间的右端点为当前区间右端点和 merged 数组中最后一个区间右端点的最大值 merged.get(merged.size() - 1)[1] = Math.max(intervals[i][1], merged.get(merged.size() - 1)[1]); } } return merged.toArray(new int[merged.size()][]); } }
//左端点升序排序 Arrays.sort(intervals, (a, b) -> { return a[0] - b[0]; }); //左端点降序排序 Arrays.sort(intervals, (a, b) -> { return b[0] - a[0]; }); //右端点升序排序 Arrays.sort(intervals, (a, b) -> { return a[1] - b[1]; }); //右端点降序排序 Arrays.sort(intervals, (a, b) -> { return b[1] - a[1]; });
Lambda 表达式是什么?
Java 8 中引入的一种新特性,用于简化匿名内部类的语法。Lambda 表达式可以看作是一个匿名函数,它允许你直接以内联的方式为函数式接口(Functional Interface)提供实现。Lambda 表达式的语法形式如下:
(parameters) -> expression
或
(parameters) -> { statements; }
①parameters 指定了 Lambda 表达式的参数列表。
②-> 是 Lambda 运算符,将参数列表和 Lambda 表达式的主体分开。
③expression 或 { statements; } 定义了 Lambda 表达式的主体,可以是一个表达式或一段代码块。
result.toArray(new int[result.size()][])
这行代码的作用是将 result 这个 LinkedList 转换为二维数组。
具体来说,result.toArray(new int[result.size()][]) 这段代码中:
①result.size() 返回了 result 中元素的个数。
②new int[result.size()][] 创建了一个新的二维数组,第一维的长度为 result.size()。
③result.toArray(new int[result.size()][]) 将 result 中的元素复制到新创建的二维数组中。
④最终的效果是将 LinkedList 转换为二维数组,以便返回合并后的区间数组。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。