X

LEETCODE 56. Merge Intervals 解题思路分析

题目大意:

合并区间

给出一个区间的集合,请合并所有重叠的区间。

示例 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] 可被视为重叠区间。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=56

解题思路分析:

本题需要先对数组进行一次排序,排序规则是区间开始坐标由小到大升序排序。排序后我们能够保证对于任意一个区间,它的开始坐标一定大于等于前区间的开始坐标,这样相邻2个区间的关系会有以下三种可能:

  1. 当前区间开始坐标大于前区间结束坐标,说明2区间不相交从而无法合并,将前区间加入返回结果。
  2. 当前区间开始坐标小于等于前区间结束坐标,说明2区间存在交集,交集范围是当前区间开始坐标到前区间结束坐标之间,此时可以合并,将前区间结束坐标更改为当前区间结束坐标。
  3. 当前区间结束坐标小于等于前区间结束坐标,说明当前区间是前区间的子集,当前区间可被忽略。

实现代码:

public int[][] merge(int[][] intervals) {
    // 如果intervals为空,返回空
    if(intervals.length==0) return new int[0][0];
    // 按区间开始坐标升序排序
    Arrays.sort(intervals, (x1, x2)->x1[0]-x2[0]);
    // 返回结果
    List<int[]> list = new ArrayList<>();
    // 前区间
    int[] pre = intervals[0];
    // 从第二个区间开始循环与前区间比较
    for(int i=1;i<intervals.length;i++){
        // 当前区间
        int[] current = intervals[i];
        // 当前区间开始坐标大于前区间结束坐标,无交集
        if(current[0] > pre[1]){
            // 将前区间加入返回结果
            list.add(pre);
            // 将当前区间设置为前区间
            pre=current;
        }else if(current[1]>=pre[1]){
            // 当前区间结束坐标大于等于前区间结束坐标
            // 另外两个以确定条件:
            // 1. 当前区间开始坐标小于等于前区间结束坐标(上面if的另外分支)
            // 2. 当前区间开始坐标大于等于前区间开始坐标(因为排序)
            // 此时2区间相交,将前区间结束坐标更改为当前区间结束坐标
            pre[1]=current[1];
        }
    }
    // 将最后一个区间加入返回结果
    list.add(pre);
    // 将list转化为数组返回
    int[][] res = new int[list.size()][2];
    for(int i=0;i<list.size();i++){
        res[i] = list.get(i);
    }
    return res;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 90.48% of Java online submissions for Merge Intervals.

Memory Usage: 40.9 MB, less than 63.77% of Java online submissions for Merge Intervals.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-56-merge-intervals-解题思路分析/
Categories: leetcode
kwantong: