福州做网站销售公司,甘肃网站seo推广,北京的做网站的公司,网站建设 江苏文章目录题目描述代码 思路更新版 2.0题目描述
重叠区间#xff1a;需要有重叠判断注意#xff1a;题目并没有说集合间有序#xff0c;因此要先做一个排序#xff0c;以左下标为排序值#xff08;否则会出错
代码 思路
经过排序后#xff0c;只需要循环一…
文章目录题目描述代码 思路更新版 2.0题目描述
重叠区间需要有重叠判断注意题目并没有说集合间有序因此要先做一个排序以左下标为排序值否则会出错
代码 思路
经过排序后只需要循环一次即可从左到右可以合并则合并不能合并则添加当前数组到答案中然后开启新的数组继续。
class Solution {public int[][] merge(int[][] intervals) {// 区间个数int len intervals.length;// 先进行排序O(nlogn)Arrays.sort(intervals,new Comparatorint[](){Overridepublic int compare(int[] a,int[] b){return a[0]-b[0];}});Listint[] ansL new ArrayList();// 先加入一个初始数组int[] first new int[2];first[0] intervals[0][0];first[1] intervals[0][1];ansL.add(first);int[] nowAL ansL.get(0);// O(n)一次遍历结束for(int i1; i len; i){// 合并判断if(over(nowAL[0],nowAL[1],intervals[i][0],intervals[i][1])){// 更新区间值判断if(intervals[i][0]nowAL[0]){nowAL[0] intervals[i][0];}if(intervals[i][1]nowAL[1]){nowAL[1] intervals[i][1];}}// 不合并则更新else{first new int[2];first[0] intervals[i][0];first[1] intervals[i][1];ansL.add(first);nowAL first;}}int[][] ans new int[ansL.size()][2];for(int i0;iansL.size();i){ans[i] ansL.get(i);}return ans;}// 重叠判断boolean over(int left1,int right1,int left2,int right2){// 不重叠的情况if(left1 right2 || left2 right1){return false;}return true;}
}更新版 2.0
class Solution {public int[][] merge(int[][] intervals) {if(intervals null || intervals.length 1) {return intervals;} Listint[] list new ArrayList();// 先排序 O(nlogN)Arrays.sort(intervals, (a, b) - (a[0] - b[0]));// 时间复杂度 O(n)每次合并第 i ~ j 个区间for(int i 0, j; i intervals.length; i j) {// 定义当前左、右区间int left intervals[i][0];int right intervals[i][1];j i 1;for(; j intervals.length right intervals[j][0]; j) {// 维护右区间right Math.max(right, intervals[j][1]);}list.add(new int[]{left, right});}return list.toArray(new int[list.size()][2]);}
}去注释最简版
class Solution {public int[][] merge(int[][] intervals) {if(intervals null || intervals.length 1) {return intervals;} Listint[] list new ArrayList();Arrays.sort(intervals, (a, b) - (a[0] - b[0]));for(int i 0, j; i intervals.length; i j) {int left intervals[i][0];int right intervals[i][1];j i 1;for(; j intervals.length right intervals[j][0]; j) {right Math.max(right, intervals[j][1]);}list.add(new int[]{left, right});}return list.toArray(new int[list.size()][2]);}
}
