C语言题解Leetcode56合并区间实例
itbird01 人气:0解题思路
题目链接 56. 合并区间
本质在于两两做对比,如果两个区间,可以合并,则为结果二维数组中的一员,如果不可合并,则放入结果二维数组,所以根本在于,如何判断两个区间,是可合并,还是不可合并
1.首先将二维数组,按照左端元素进行排序
2.将第一个元素放入结果区间列表
3.如果当前区间的左端元素比结果区间列表最后一个区间右端元素小,则存在包含关系,此时只需更新右端元素即可 (更新为当前区间的右端元素与结果区间的右端元素的最大值)
4.如果不包含,则将当前区间加入结果区间列表,作为最后一个区间 5.输出结果区间列表
解题遇到的问题
1.二维数组排序
2.二维数组在不知道大小时,如何初始化?
后续需要总结学习的知识点
- Arrays.copyOf源码和使用方法总结
- 二维数组排序、重新compare
## 解法1 class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); int index = 0; for (int i = 1; i < intervals.length; i++) { if (intervals[index][1] < intervals[i][0]) { index++; intervals[index][0] = intervals[i][0]; intervals[index][1] = intervals[i][1]; } else { intervals[index][1] = Math.max(intervals[i][1], intervals[index][1]); } } return Arrays.copyOf(intervals, index + 1); } }
加载全部内容