LeetCode算法题-合并区间
题目描述: 给出一个区间的集合,请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路分析:
- 对给出的二维数组进行排序,使得满足每一组第一个元素都小于等于后面一组第一个元素,例如这种形式:
[[1,3],[2,6],[8,10]]
。[[1,3],[8,10],[2,6]]
这种形式则需要调整。 - 贪心给出一个新的结果二维数组,每次去和已知数组比较,发生重合则重组后加入结果数组,否则则将已知数组的拷贝过来。
代码如下:
public static int[][] merge(int[][] intervals) {
if (intervals.length==0) return new int[][]{};
if (intervals.length ==1) return intervals;
//处理输入,使得每一个里面的第一个元素递增
for (int i=0; i<intervals.length-1; i++){
for (int j=0; j<intervals.length-1-i; j++){
if (intervals[j][0] > intervals[j+1][0]){
int[] tmp = intervals[j];
intervals[j] = intervals[j+1];
intervals[j+1] = tmp;
}
}
}
int[][] out = new int[intervals.length][2];
out[0] = intervals[0];
int count1 = 0;
for (int i=1; i<intervals.length; i++){
if (out[count1][1] < intervals[i][0]) out[++count1]=intervals[i];
else out[count1] = new int[]{out[count1][0], Math.max(intervals[i][1],out[count1][1])};
}
return Arrays.copyOfRange(out,0,count1+1);
}
总结
这种方法第2步不花时间,重点是第一步的冒泡排序时间太多了。这一题是中等难度题目,难度还是有的。
执行结果:
通过
显示详情
执行用时 :205 ms, 在所有 Java 提交中击败了7.40% 的用户
内存消耗 :51.4 MB, 在所有 Java 提交中击败了12.37%的用户
阅读次数: 本文累计被阅读 1000000 次