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

leetcode 56合并区间

news 2025/7/7 12:16:58

思路

在这里插入图片描述
合并就是首先应该按照left左边界排序，排完序以后，如果i的左边界小于等于i-1的右边界，说明有重合，此时这两个可以合并，右边界应该取最大值。

代码

排序

我是定义了一个类,存储左右边界，先将数组转化为这个Interval数组，因为我不会二维数组排序

class Interval{int left;int right;}

排序：

 Arrays.sort(intervalss, new Comparator<Interval>() {@Overridepublic int compare(Interval o1, Interval o2) {if (o1.left == o2.left){return o1.right -o2.right;}return o1.left - o2.left;}});

后来学习了二维数组排序

Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}
});

进行区间合并

  		int min_left = intervalss[0].left;  //每一次合并的左边界int max_right = intervalss[0].right;//每一次合并的右边界for (int i = 1; i < intervalss.length ; i++) {if (intervalss[i].left> max_right ){ //新的最左边的值大于之前的最右边的值，说明连不起来，后面的需要作为一个新的区间,还有就是最后一个，应该直接作为一个新的区间List<Integer> list = new ArrayList<>(2);list.add(min_left);list.add(max_right);list2D.add(list);min_left = intervalss[i].left;max_right = intervalss[i].right;}else {max_right =Math.max(max_right, intervalss[i].right);}}List<Integer> list = new ArrayList<>(2); //不要忘了对最后一次合并处理，放入结果里面list.add(min_left);list.add(max_right);list2D.add(list);

全部代码：

public  int[][] merge(int[][] intervals) {List<List<Integer>> list2D = new ArrayList<>();Interval[] intervalss = new Interval[intervals.length];for (int i = 0; i < intervals.length; i++) {intervalss[i] = new Interval();intervalss[i].left = intervals[i][0];intervalss[i].right = intervals[i][1];}Arrays.sort(intervalss, new Comparator<Interval>() {@Overridepublic int compare(Interval o1, Interval o2) {if (o1.left == o2.left){return o1.right -o2.right;}return o1.left - o2.left;}});Arrays.stream(intervalss).forEach(a -> System.out.println(a.left + " " + a.right));int min_left = intervalss[0].left;int max_right = intervalss[0].right;for (int i = 1; i < intervalss.length ; i++) {if (intervalss[i].left> max_right ){ //新的最左边的值大于之前的最右边的值，说明连不起来，后面的需要作为一个新的区间,还有就是最后一个，应该直接作为一个新的区间List<Integer> list = new ArrayList<>(2);list.add(min_left);list.add(max_right);list2D.add(list);min_left = intervalss[i].left;max_right = intervalss[i].right;}else {max_right =Math.max(max_right, intervalss[i].right);}}List<Integer> list = new ArrayList<>(2); //不要忘了对最后一次合并处理，放入结果里面list.add(min_left);list.add(max_right);list2D.add(list);int[][] result = new int[list2D.size()][];for (int i = 0;i< list2D.size();i++){result[i] = new int[]{list2D.get(i).get(0), list2D.get(i).get(1)};}return result;}class Interval{int left;int right;}