leetcode 056： 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
-
1 <= intervals.length <= 104 -
intervals[i].length == 2 -
0 <= starti <= endi <= 104
Related Topics
数组
排序
思路1 ： 排序加暴力破解
public int[][] merge(int[][] intervals) {
int[] flag = new int[intervals.length];
HashMap<Integer,Integer> map = new HashMap<>();
//对区间排序 插入排序
for(int i = 1 ; i < intervals.length;i++){
for(int j = i; j > 0 && intervals[j][0] < intervals[j-1][0]; j --){
int[] temp = intervals[j];
intervals[j] = intervals[j-1];
intervals[j-1] = temp;
}
}
for(int i = 0; i < intervals.length;i++){
//表示i已经并合并
if(flag[i] == 1){
continue;
}
flag[i] = 1;
for(int j = i + 1; j < intervals.length;j++){
if(flag[j] == 1){
continue;
}
//判断是否需要合并
//当i的左边界大于j的右边界 i的右边界小于j的左边界 不需要合并
if(intervals[i][0] > intervals[j][1] || intervals[i][1] < intervals[j][0]){
}else{
if(intervals[i][0] > intervals[j][0]){
intervals[i][0] = intervals[j][0];
}
if(intervals[i][1] < intervals[j][1]){
intervals[i][1] = intervals[j][1];
}
flag[j] = 1;
}
}
//此时i里面存储的最终合并的结果
map.put(intervals[i][0],intervals[i][1]);
}
int[][] result = new int[map.size()][2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
result[index][0] = entry.getKey();
result[index][1] = entry.getValue();
index++;
}
return result;
}
执行耗时:297 ms,击败了5.17% 的Java用户
内存消耗:45.8 MB,击败了5.02% 的Java用户
对上面的思路进行优化，因为已经排序过 ，当无法合并的时候，后续也不需要判断。
跟上面比起来，性能虽然提升很大，但还是相对较差。
public int[][] merge(int[][] intervals) {
HashMap<Integer,Integer> map = new HashMap<>();
//对区间排序 插入排序
for(int i = 1 ; i < intervals.length;i++){
for(int j = i; j > 0 && intervals[j][0] < intervals[j-1][0]; j --){
int[] temp = intervals[j];
intervals[j] = intervals[j-1];
intervals[j-1] = temp;
}
}
for(int i = 0; i < intervals.length;i++){
//因为已经排序过 所以 当j的左边界大于i的右边界时 后面的就无需判断
int j;
for(j = i + 1; j < intervals.length && intervals[i][1] >= intervals[j][0];j++){
if(intervals[i][1] < intervals[j][1]){
intervals[i][1] = intervals[j][1];
}
}
//[i,j)范围内已合并完毕
//此时i里面存储的最终合并的结果
map.put(intervals[i][0],intervals[i][1]);
i = j-1;
}
int[][] result = new int[map.size()][2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
result[index][0] = entry.getKey();
result[index][1] = entry.getValue();
index++;
}
return result;
}
解答成功:
执行耗时:172 ms,击败了5.17% 的Java用户
内存消耗:45.9 MB,击败了5.02% 的Java用户
使用jdk提供的排序算法进行优化，性能有了明显的提升。
public int[][] merge(int[][] intervals) {
//排序 由于自己写的插入排序相比jdk中的排序算法性能相对较差 使用arrays中的sort排序
HashMap<Integer,Integer> map = new HashMap<>();
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
for(int i = 0; i < intervals.length;i++){
//因为已经排序过 所以 当j的左边界大于i的右边界时 后面的就无需判断
int j;
for(j = i + 1; j < intervals.length && intervals[i][1] >= intervals[j][0];j++){
if(intervals[i][1] < intervals[j][1]){
intervals[i][1] = intervals[j][1];
}
}
//[i,j)范围内已合并完毕
//此时i里面存储的最终合并的结果
map.put(intervals[i][0],intervals[i][1]);
i = j-1;
}
int[][] result = new int[map.size()][2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
result[index][0] = entry.getKey();
result[index][1] = entry.getValue();
index++;
}
return result;
}
思路2：参考leetcode
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
ArrayList<int[]> list = new ArrayList<>();
for(int i = 0 ;i < intervals.length;i++){
int left = intervals[i][0];
int right = intervals[i][1];
//如果当前的左边界大于合并中最后一个的右边界 说明不需要合并
if(list.size() == 0 || left > list.get(list.size() - 1)[1]){
list.add(new int[]{left,right});
}else{//需要合并
list.get(list.size()-1)[1] = Math.max(list.get(list.size()-1)[1],right);
}
}
return list.toArray(new int[list.size()][]);