资讯专栏INFORMATION COLUMN

leetcode56 Merge Intervals

shmily / 1433人阅读

摘要:题目要求输入一系列区间,将出现交叉的区间合并起来,并将合并后的区间返回。将这两个数组分别排序可以得到和。也就是说,合并后的结果和是等价的。举个栗子,输入为,先判断是否是独立区间,可见可以和合并,则将修改为。

题目要求
Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

输入一系列区间,将出现交叉的区间合并起来,并将合并后的区间返回。这里需要注意的是,区间的大小顺序无关,即输出为[1,2],[3,4]和[3,4],[1,2]都是可以的

思路一:简单粗暴利用排序API

第一次看到这道题目,难免就会想到,将这些区间按照开始值有小到大排序,然后依次比较前后两个区间的开始值和结束值,如果出现重叠,则将两个区间合并。
在这里先介绍一下,java中的两种利用API进行排序的方法。
当排序对象是数组时,可以使用Arrays.sort机制,它的核心实现在于Comparable接口。任何一个实现了该接口的数组中的成员都可以使用Arrays.sort方法。
当排序对象是集合时,可以使用list.sort方法。它的核心实现在于Comparator接口。通过该接口可以实现集合的排序。
在这里不详细介绍这二者的内核和具体实现,有兴趣的可以查看java API。
代码实现如下:

    public List merge(List intervals) {
        List result = new ArrayList();
        if( intervals.size() == 0){
            return result;
        }
        intervals.sort(new Comparator(){
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start < o2.start){
                    return -1;
                }else if(o1.start > o2.start){
                    return 1;
                }
                
                return 0;
            }    
        });
        
        result.add(intervals.get(0));
        for(int i = 1 ; i previous.end ? temp.end : previous.end;
            }else{
                result.add(temp);
            }
        }
        
        return result;
    }
思路二:简化排序

对对象的排序其实相当的影响效率和性能。其实这题的问题跳脱出来看,无需知道特定的区间,只要知道所有的按顺序的起始值和终点值。
例如输入为[1,3],[5,6],[2,7]
如果按照思路一,则需要先将对象排序,得出[1,3],[2,7],[5,6],然后再依次判断是否需要合并临近区间。
按照思路二,我们直接将区间看成起始值列表[1,5,2]和结束值列表[3,6,7]。将这两个数组分别排序可以得到[1,2,5]和[3,6,7]。也就是说,[1,3],[5,6],[2,7]合并后的结果和[1,3],[2,6],[5,7]是等价的
为什么呢?因为如果两个区间重叠,那么这两个区间的一个结束值和一个开始值必然不会出现在结果集中,也就是说,我只需要找到这两个区间的一个最小值和一个最大值就可以了。如果是n个区间重叠,那么只要找这n个区间的最小值和最大值就可以了。同理,如果一个区间和任何一个区间都不会发生合并,它的开始值和结束值就必然会在排序后两个数组中处于相同下标的位置。且其结果值一定小于下一个下标的开始值。
按照这种思路,实现的代码如下:

    public List merge2(List intervals) {
        if(intervals == null || intervals.size() < 2)
            return intervals;
        List res = new ArrayList<>();
        int len = intervals.size();
        int[] starts = new int[len], ends = new int[len];
        for(int i = 0; i < len; i++){
            starts[i] = intervals.get(i).start;
            ends[i] = intervals.get(i).end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        
        int start = starts[0], end = ends[0];
        for(int i = 0; i < len - 1; i++){
            if(ends[i] >= starts[i + 1]){
                end = ends[i + 1];
            }
            else{
                end = ends[i];
                res.add(new Interval(start, end));
                start = starts[i + 1];
                end = ends[i + 1];
            }
        }
        res.add(new Interval(start, end));
        return res;
    }

可以看到,该算法的时间复杂度为O(4n)

思路三:无需排序的算法

这个答案参考了一下高分回答。整理了一下思路如下:
其实在这里无需对各个区间排序。只需要将需要合并的区间合并起来即可。如果经过判断是独立的区间,则将该区间加入结果集,如果不是独立的区间,则将该区间合并至后续的区间并继续判断下一个区间在剩余的区间中是否是独立的区间。
举个栗子,输入为[1,3],[5,6],[10,11],[2,7],
先判断[1,3]是否是独立区间,可见[1,3]可以和[2,7]合并,则将[2,7]修改为[1,7]。
接着判断[5,6]是否可以合并至后面的区间,发现需要将[5,6]与[1,7]合并,合并为[1,7]。
最后,还剩下[10,11]和[1,7]可以先后加入结果集。
代码如下:

    public List merge3(List intervals) {
           int size = intervals.size();
            if (size < 2) {
                return intervals;
            }
            
            List result = new ArrayList(size);
            Interval[] array = intervals.toArray(new Interval[size]);
            
            for (int f = 0; f < size; f++) {
                Interval first = array[f];
                boolean add = true;
                for (int s = f + 1; s < size; s++) {
                    Interval second = array[s];
                    if (first.end < second.start || first.start > second.end) {
                        continue;
                    }

                    if (first.start <= second.start) {
                        second.start = first.start;
                    }
                    if (first.end >= second.end) {
                        second.end = first.end;
                    }
                    add = false;
                    break;
                }
                
                if (add) {
                    result.add(first);
                }
            }
            return result;
        }


想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/70123.html

相关文章

  • 力扣(LeetCode)56

    摘要:题目地址题目描述给出一个区间的集合,请合并所有重叠的区间。示例输入输出解释区间和重叠将它们合并为示例输入输出解释区间和可被视为重叠区间。解答按照区间起始节点排序。否则把列表最后一个区间和当前区间合并。 题目地址:https://leetcode-cn.com/probl...题目描述:给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10]...

    OBKoro1 评论0 收藏0
  • [LeetCode/LintCode] Merge Intervals

    摘要:方法上没太多难点,先按所有区间的起点排序,然后用和两个指针,如果有交集进行操作,否则向后移动。由于要求的,就对原数组直接进行操作了。时间复杂度是的时间。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

    gougoujiang 评论0 收藏0
  • [Leetcode] Merge Intervals and Insert Interval 合并间

    摘要:我们只要把所有和该有重叠的合并到一起就行了。最后把前半部分的列表,合并后的大和后半部分的列表连起来,就是结果了。 Merge Intervals 最新更新请见 https://yanjia.me/zh/2019/02/... Given a collection of intervals, merge all overlapping intervals.For example, Gi...

    antyiwei 评论0 收藏0
  • leetcode--57--Insert Interval

    摘要:问题描述分析这道题的关键在于理解问题,抽取原型,理解中间可以部分如何界定,以及非部分如何进行追加。需要注意的是循环到最后一个元素和在最后一个元素的区别。 问题描述: Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You m...

    kycool 评论0 收藏0

发表评论

0条评论

shmily

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<