当前位置：首页 > news >正文

2025年- H12-Lc119-56.合并区间（普通数组）---java版

news 2025/4/30 9:20:33

1.题目描述

在这里插入图片描述

2.思路

思路参考了代码随想录：

按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）
如果有合并，则把合并区间加入到结果数组中，如果没有合并，则将该区间加入到数组中。

例子：
在这里插入图片描述

在这里插入图片描述
return res.toArray(new int[res.size()][]);
//将 LinkedList<int[]> 转换成 int[][] 数组作为最终结果返回。

补充2：
在这里插入图片描述

补充3：
在这里插入图片描述

3.代码实现

方法1：不带测试用例

class Solution {public int[][] merge(int[][] intervals) {//?创建一个链表，res是动态的，可以随时插入和删除数组LinkedList<int[]> result=new LinkedList<>();//先将无序的二维数组，用自定义的规则进行排序，注意这块内容不熟练。将二维数组的左区间进行排序。Arrays.sort(intervals,(a1,a2)->Integer.compare(a1[0],a2[0]));//将第一个区间加入到res中，用于后序区间的比较和合并result.add(intervals[0]);//进行比较，如果第一个区间的右边界小于第二个区间的左边界，则进行合并//二维数组可以看作一维数组的数组，i从第二个元素开始（i=1），因为第一个元素（i=0）已经加入到res中for(int i=1;i<intervals.length;i++){if(result.getLast()[1]>=intervals[i][0]){//开始判断新区间的起始位置和结束位置,因为经过排序后，左边界的最小值是res一开始加入的区间的左边界int begin=result.getLast()[0];int end=Math.max(result.getLast()[1],intervals[i][1]);//删除原来的旧区间result.remove(result.getLast());// result.removeLast();//将合并的新区间（一维数组）加入到res中,result.add(new int[]{begin,end});}else{//如果两个区间不重合，直接把当前区间(Y一维数组）加入到结果数组中result.add(intervals[i]);}}return result.toArray(new int[result.size()][]);}}

方法二：带测试用例

import java.util.Arrays;
import java.util.LinkedList;public class H56 {public int[][] merge(int[][] intervals) {//?创建一个链表，res是动态的，可以随时插入和删除数组LinkedList<int[]> result=new LinkedList<>();//先将无序的二维数组，用自定义的规则进行排序，注意这块内容不熟练。将二维数组的左区间进行排序。Arrays.sort(intervals,(a1,a2)->Integer.compare(a1[0],a2[0]));//将第一个区间加入到res中，用于后序区间的比较和合并result.add(intervals[0]);//进行比较，如果第一个区间的右边界小于第二个区间的左边界，则进行合并//二维数组可以看作一维数组的数组，i从第二个元素开始（i=1），因为第一个元素（i=0）已经加入到res中for(int i=1;i<intervals.length;i++){if(result.getLast()[1]>=intervals[i][0]){//开始判断新区间的起始位置和结束位置,因为经过排序后，左边界的最小值是res一开始加入的区间的左边界int begin=result.getLast()[0];int end=Math.max(result.getLast()[1],intervals[i][1]);//删除原来的旧区间result.remove(result.getLast());//result.removeLast();//将合并的新区间（一维数组）加入到res中,result.add(new int[]{begin,end});}else{//如果两个区间不重合，直接把当前区间(Y一维数组）加入到结果数组中result.add(intervals[i]);}}return result.toArray(new int[result.size()][]);}public static void main(String[] args){H56 test2=new H56();int[][] intervals={{1,3},{2,6},{8,10},{15,18}};int[][] res=test2.merge(intervals);System.out.println("合并后的区间结果：");for(int[] m:res){//m本来是1维数组带花括号,打印成中括号的1维数组System.out.println(Arrays.toString(m));}}}