Leetcode之合并区间

问题描述

给出一个区间的集合，请合并所有重叠的区间。

示例 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] 可被视为重叠区间。

提示：

intervals[i][0] <= intervals[i][1]

问题解法

首先使用冒泡排序对集合进行排序。当确定第I个最小初始端点的时候，判断它是否与第I-1个区间进行合并。

class Solution { public int[][] merge(int[][] intervals) { if(intervals==null) return null; boolean[] flags=new boolean[intervals.length]; int num=0; for(int i=0;i<intervals.length;i++) { //排序 for(int j=i+1;j<intervals.length;j++) { if(intervals[j][0]<intervals[i][0]) { //交换 int temp1=intervals[j][0]; int temp2=intervals[j][1]; intervals[j][0]=intervals[i][0]; intervals[j][1]=intervals[i][1]; intervals[i][0]=temp1; intervals[i][1]=temp2; } } if(i!=0) { if(intervals[i][0]>intervals[i-1][1]) {//两个区间 flags[i]=true; }else { intervals[i][0]=intervals[i-1][0];//合并成一个区间 intervals[i][1]=Math.max(intervals[i-1][1], intervals[i][1]); flags[i-1]=false; flags[i]=true; num--; } }else { flags[i]=true; } num++; } int[][] re=new int[num][2]; for(int i=0,j=0;i<flags.length;i++) { if(flags[i]) re[j++]=intervals[i]; } return re; } }

运行结果

官方题解

class Solution { public int[][] merge(int[][] intervals) { List<int[]> res = new ArrayList<>(); if (intervals.length == 0 || intervals == null) return res.toArray(new int[0][]); // 对起点进行排序 Arrays.sort(intervals, (a, b) -> a[0] - b[0]); int i = 0; while (i < intervals.length) { int left = intervals[i][0]; int right = intervals[i][1]; // 如果有重叠，循环判断哪个终点满足条件 while (i < intervals.length - 1 && intervals[i + 1][0] <= right) { i++; right = Math.max(right, intervals[i][1]); } // 将现在的区间放进res里面 res.add(new int[]{left, right}); // 接着判断下一个区间 i++; } return res.toArray(new int[0][]); } }

看完官方题解之后，我对我的排序方法做了调整：

class Solution { public int[][] merge(int[][] intervals) { if(intervals==null) return null; boolean[] flags=new boolean[intervals.length]; int num=0; Arrays.sort(intervals,(a,b)->a[0]-b[0]); for(int i=0;i<intervals.length;i++) { if(i!=0) { if(intervals[i][0]>intervals[i-1][1]) {//两个区间 flags[i]=true; }else { intervals[i][0]=intervals[i-1][0];//合并成一个区间 intervals[i][1]=Math.max(intervals[i-1][1], intervals[i][1]); flags[i-1]=false; flags[i]=true; num--; } }else { flags[i]=true; } num++; } int[][] re=new int[num][2]; for(int i=0,j=0;i<flags.length;i++) { if(flags[i]) re[j++]=intervals[i]; } return re; } }

总结

java 排序时可使用Arrays.sort排序方法。Comparator接口返回值为正数时表示交换。负数表示不换。