1. 首页
  2. Leetcode经典148题

leetCode-57-Insert-Interval

题目描述(困难难度)

leetCode-57-Insert-Interval

上一道可以说是一个问题,只不过这个是给一个已经合并好的列表,然后给一个新的节点依据规则加入到合并好的列表。

解法一

对应 56 题的解法一,没看的话,可以先过去看一下。这个问题其实就是我们解法中的一个子问题,所以直接加过来就行了。

public List<Interval> insert(List<Interval> intervals, Interval newInterval) { 
            Interval start = null;
            Interval end = null;
            int i_start = newInterval.start;
            int i_end =newInterval.end;
            int size = intervals.size();
            List<Interval> in = new ArrayList<>(); 
            //遍历合并好的列表
            for (int j = 0; j < size; j++) {
                if (i_start >= intervals.get(j).start && i_start <= intervals.get(j).end) {
                    start = intervals.get(j);
                }
                if (i_end >= intervals.get(j).start && i_end <= intervals.get(j).end) {
                    end = intervals.get(j);
                }
                if (i_start < intervals.get(j).start && i_end >intervals.get(j).end) {
                    in.add(intervals.get(j));
                } 

            }
            if (in.size() != 0) { 
                for (int index = 0; index < in.size(); index++) {
                    intervals.remove(in.get(index));
                } 
            }
            Interval interval = null;
            //根据不同的情况,生成新的节点
            if (equals(start, end)) {
                int s = start == null ? i_start : start.start;
                int e = end == null ? i_end : end.end;
                interval = new Interval(s, e); 
            } else if (start!= null && end!=null) {
                interval = new Interval(start.start, end.end); 
            }else if (start == null) {
                interval = new Interval(i_start, i_end); 
            }
            if (start != null) {
                intervals.remove(start);
            }
            if (end != null) {
                intervals.remove(end);
            }
           //不同之处是生成的节点,要遍历原节点,根据 start 插入到对应的位置,虽然题目没说,但这里如果不按顺序插入的话,leetcode 过不了。
            for(int i = 0;i<intervals.size();i++){
                if(intervals.get(i).start>interval.start){
                    intervals.add(i,interval);
                    return intervals;
                }
            }
            intervals.add(interval);
            return intervals;
        }
private boolean equals(Interval start, Interval end) { 
    if (start == null && end == null) {
        return false;
    }
    if (start == null || end == null) {
        return true;
    }
    if (start.start == end.start && start.end == end.end) {
        return true;
    }
    return false;
}

时间复杂度:O(n)。

空间复杂度: O(n), 里边的 in 变量用来存储囊括的节点时候耗费的。

我们其实可以利用迭代器,一边遍历,一边删除,这样就不需要 in 变量了。

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        Interval start = null;
        Interval end = null;
        int i_start = newInterval.start;
        int i_end = newInterval.end;  
        //利用迭代器遍历
        for (Iterator<Interval> it = intervals.iterator(); it.hasNext();) {
            Interval inter = it.next();
            if (i_start >= inter.start && i_start <= inter.end) {
                start = inter;
            }
            if (i_end >= inter.start && i_end <= inter.end) {
                end = inter;
            }
            if (i_start < inter.start && i_end > inter.end) {

                it.remove();
            }
        }
        Interval interval = null;
        if (equals(start, end)) {
            int s = start == null ? i_start : start.start;
            int e = end == null ? i_end : end.end;
            interval = new Interval(s, e);
        } else if (start != null && end != null) {
            interval = new Interval(start.start, end.end);
        } else if (start == null) {
            interval = new Interval(i_start, i_end);
        }
        if (start != null) {
            intervals.remove(start);
        }
        if (end != null) {
            intervals.remove(end);
        }
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).start > interval.start) {
                intervals.add(i, interval);
                return intervals;
            }
        }
        intervals.add(interval);
        return intervals; 
    }

private boolean equals(Interval start, Interval end) { 
    if (start == null && end == null) {
        return false;
    }
    if (start == null || end == null) {
        return true;
    }
    if (start.start == end.start && start.end == end.end) {
        return true;
    }
    return false;
}

时间复杂度:O(n)。

空间复杂度: O(1)。

解法二

对应 56 题的解法二,考虑到它给定的合并的列表是有序的,和解法二是一个思想。只不过这里不能直接从末尾添加,而是根据新节点的 start 来找到它应该在的位置,然后再利用之前的想法就够了。

这里把 leetcode 里的两种写法,贴过来,大家可以参考一下。

第一种

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> result = new LinkedList<>();
    int i = 0;
    // 将新节点之前的节点加到结果中
    while (i < intervals.size() && intervals.get(i).end < newInterval.start)
        result.add(intervals.get(i++));
    // 和新节点判断是否重叠,更新新节点
    while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
        newInterval = new Interval( 
                Math.min(newInterval.start, intervals.get(i).start),
                Math.max(newInterval.end, intervals.get(i).end));
        i++;
    }
    //将新节点加入
    result.add(newInterval); 
    ///剩下的全部加进来
    while (i < intervals.size()) result.add(intervals.get(i++)); 
    return result;
}

第二种。和之前是一样的思想,只不过更加的简洁,可以参考一下。

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> result = new ArrayList<Interval>();
    for (Interval i : intervals) {
        //新加的入的节点在当前节点后边
        if (newInterval == null || i.end < newInterval.start)
            result.add(i);
        //新加入的节点在当前节点的前边
        else if (i.start > newInterval.end) {
            result.add(newInterval);
            result.add(i);
            newInterval = null;
        //新加入的节点和当前节点有重合,更新节点
        } else {
            newInterval.start = Math.min(newInterval.start, i.start);
            newInterval.end = Math.max(newInterval.end, i.end);
        }
    }
    if (newInterval != null)
        result.add(newInterval);
    return result;
}

总的来说,上边两个写法本质是一样的,就是依据他们是有序的,先把新节点前边的节点加入,然后开始判断是否重合,当前节点加入后,把后边的加入就可以了。

时间复杂度:O(n)。

空间复杂度:O(n),存储最后的结果。

总的来说,这道题可以看做上道题的一些变形,本质上是一样的。由于用 for 循环不能一边遍历列表,一边删除某个元素,所以利用迭代器实现边遍历,边删除,自己也是第一次用。此外,解法一更加通用些,它不要求给定的列表有序。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-57-Insert-Interval

链接:https://www.javajike.com/article/3194.html

« leetCode-56-Merge-Intervals
leetCode-58-Length-of-Last-Word»

相关推荐

QR code