房产网站系统哪个好_现在出入郑州最新规定_免费建设个人网站_网络推广平台几大类

1、题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

2、解答思路

本题需要求解合并区间，虽然题目中给的示例是按照第一个元素排序的，但是题目中并没有说明这个条件，因此我们首先需要对数组按照第一个元素进行排序，之后的工作就简单很多了。利用[min, max]代表合并后的数组，数组不能重叠的条件只有一个：左边界 > max，之后分情况讨论可以重叠和不能重叠即可。

• 左边界 <= max， 即当前数组可以重叠到前面的数组：更新合并后的数组的右边界，即max的值。然后继续遍历看之后的数组能否继续合并。
• 左边界 > max，即当前数组不能重叠到前面的数组：将前面合并后的数组存储到结果数组ans中，然后将元素赋值给min和max，继续讨论。

class Solution {public int[][] merge(int[][] intervals) {int len = intervals.length;int[][] ans = new int[len][2];int max,min,index;// 按照数组的第一个元素对数组进行排序Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});min = intervals[0][0];max = intervals[0][1];index = 0;for(int i=1; i<len;i++) {// 左边界>最大值，则不能重叠if(intervals[i][0]>max) {ans[index][0] = min;ans[index++][1] = max;min = intervals[i][0];max = intervals[i][1];} else {max = Math.max(max, intervals[i][1]);}}// 最后记得存储到ans数组中ans[index][0] = min;ans[index++][1] = max;// 返回下标0到index的子数组，不包括indexreturn Arrays.copyOfRange(ans, 0, index);}
}

• 本题的难点在于按照数组的第一个元素对数组进行排序。
  new Comparator<int[]>()：实现了Comparator<int[]>接口，用于定义两个对象之间的比较逻辑。
  compare(int[] interval1, int[] interval2)：是Comparator接口中必须实现的方法，接收两个参数并返回一个整数来表示这两个对象的比较结果。如果返回值小于0，则表示interval1应该排在interval2之前。如果返回值等于0，则表示interval1和interval2在排序顺序中是相等的。如果返回值大于0，则表示interval1应该排在interval2之后。
• 存储结果不仅可以用数组，也可以使用列表，更易于添加元素，但是返回结果时需要转换为二维数组。
• 时间复杂度：O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(nlogn)。