潍坊网站建设平台,学生成绩管理系统 网站建设,中源建设有限公司网站,昆山营销型网站建设这道题我想了一会儿#xff0c;实在想不到比较好的算法#xff0c;只能硬着头皮写了#xff0c;然后不断的debug#xff0c;经过我不懈的努力#xff0c;最后还是AC#xff0c;不过效率确实低。
我就是按照最直接的方法来#xff0c;先把intervals数组按照第一个数star…
这道题我想了一会儿实在想不到比较好的算法只能硬着头皮写了然后不断的debug经过我不懈的努力最后还是AC不过效率确实低。
我就是按照最直接的方法来先把intervals数组按照第一个数start来排序这个是通过定义一个sort方法用冒泡排序实现的然后用一个Listint[]来装答案先把intervals[0]放进答案用index表示list中最新放入的那个答案的索引(ans.get(index))然后从i1开始遍历intervals[i]因为我这个intervals是排过序的所以后面的intervals[i]的start一定大于等于前面的intervals[i]的start但是如果intervals[i][0]比最新放入答案的intervals[i][1](ans.get(index)[1])还小说明intervals[i][0]应该在刚放入的最新答案(ans.get(index))的区间之中所以我们要去更改那个最新的答案(ans.get(index))的end把ans.get(index)[1]改为当前元素的end和他自己的end的最大值这样就可以确保区间无重叠且完整以下是我的代码
class Solution {public int[][] merge(int[][] intervals) {int n intervals.length;int index -1;sort(intervals);Listint[] ans new ArrayListint[]();ans.add(intervals[0]);index;for(int i1;in;i){if(intervals[i][0] ans.get(index)[1]){ans.get(index)[1] Math.max(ans.get(index)[1], intervals[i][1]);}else{ans.add(intervals[i]);index;}}int size ans.size();int[][] res new int[size][2];for(int i0;isize;i){res[i] ans.get(i);}return res;}public void sort(int[][] intervals){int n intervals.length;for(int i0;in;i){for(int ji1;jn;j){if(intervals[i][0] intervals[j][0]){int[] tmp new int[]{intervals[i][0], intervals[i][1]};intervals[i][0] intervals[j][0];intervals[i][1] intervals[j][1];intervals[j][0] tmp[0];intervals[j][1]tmp[1];}}}}
}
一看题解我都惊了我去和我的想法一摸一样我还以为我这种方法很low原来这是官方解法以下是题解代码
class Solution {public int[][] merge(int[][] intervals) {if (intervals.length 0) {return new int[0][2];}Arrays.sort(intervals, new Comparatorint[]() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});Listint[] merged new ArrayListint[]();for (int i 0; i intervals.length; i) {int L intervals[i][0], R intervals[i][1];if (merged.size() 0 || merged.get(merged.size() - 1)[1] L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}
原理和我的算法是一模一样的不一样的是他没有自己定义排序方法而是用了Array.sort()方法然后重写compare()方法,比较数组中第一个元素也就是strat就可以然后他也没用index来记录刚放进去的最新答案而是通过merged.get(merged.size()-1)来获得这个刚放进去的最新答案。
