成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Merge Intervals and Insert Interval 合并間

antyiwei / 2596人閱讀

摘要：我們只要把所有和該有重疊的合并到一起就行了。最后把前半部分的列表，合并后的大和后半部分的列表連起來，就是結(jié)果了。

Merge Intervals 最新更新請見 https://yanjia.me/zh/2019/02/... 
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].
排序法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(N)

思路

首先根據(jù)Interval的起點(diǎn)，我們將其排序，這樣能合并的Interval就一定是相鄰的了：

[1,3] [5,6] [2,3]
---> [1,3] [2,3] [5,6]

然后我們就順序遍歷這個(gè)列表，并記錄一個(gè)當(dāng)前待合并的Interval，如果遍歷到的Interval和當(dāng)前待合并的Interval有重復(fù)部分，我們就將兩個(gè)合并，如果沒有重復(fù)部分，就將待合并的Interval加入結(jié)果中，并用新的Interval更新這個(gè)待合并的Interval。因?yàn)閿?shù)組已經(jīng)排過序，前面的Interval的起點(diǎn)肯定小于后面Interval的起點(diǎn)，所以在判斷是否有重疊部分時(shí)，只要考慮待合并的Interval的終點(diǎn)和遍歷到的Interval的起點(diǎn)的關(guān)系就行了。

注意

判斷重疊的邊界時(shí)包含等于的情況

循環(huán)后還要把最后一個(gè)待合并的Interval也加入結(jié)果中

更新待合并Interval的邊界時(shí)，要同時(shí)更新起點(diǎn)和終點(diǎn)

代碼 
public class Solution {
    public List merge(List intervals) {
        List res = new LinkedList();
        if(intervals.size() == 0){
            return res;
        }
        // 按照起點(diǎn)排序
        Collections.sort(intervals, new Comparator(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        // 拿出第一個(gè)待合并的Interval
        Interval curr = intervals.get(0);
        for(Interval itv : intervals){
            // 如果有重疊部分，更新待合并的Interval的起點(diǎn)和終點(diǎn)
            if(curr.end >= itv.start){
                curr.start = Math.min(curr.start, itv.start);
                curr.end = Math.max(curr.end, itv.end);
            } else {
            // 否則將待合并的Interval加入結(jié)果中，并選取新的待合并Interval
                res.add(curr);
                curr = itv;
            }
        }
        // 將最后一個(gè)待合并的加進(jìn)結(jié)果
        res.add(curr);
        return res;
    }
}
Insert Interval 最優(yōu)解請見：https://yanjia.me/zh/2019/02/... 
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.


Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].


Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].


This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
排序法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(N)

思路

和Merge Interval的思路接近，這題中我們只有一個(gè)待合并的Interval，就是輸入給出的。我們只要把所有和該Interval有重疊的合并到一起就行了。為了方便操作，對于那些沒有重疊部分的Interval，我們可以把在待合并Interval之前的Interval加入一個(gè)列表中，把之后的Interval加入另一個(gè)列表中。最后把前半部分的列表，合并后的大Interval和后半部分的列表連起來，就是結(jié)果了。

注意

因?yàn)榇喜⒌腎nterval出現(xiàn)的位置不確定，判斷重疊與否時(shí)既要判斷起點(diǎn)，也要判斷終點(diǎn)

原列表為空時(shí)，直接加入待合并的Interval后返回

代碼 
public class Solution {
    public List insert(List intervals, Interval newInterval) {
        List before = new LinkedList();
        List after = new LinkedList();
        List res = new LinkedList();
        if(intervals.size() == 0){
            res.add(newInterval);
            return res;
        }
        // 排序
        Collections.sort(intervals, new Comparator(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        for(Interval itx : intervals){
            // 將待合并Interval之前的存入一個(gè)列表中
            if(newInterval.start > itx.end){
                before.add(itx);
            }
            // 將有重疊的Interval都合并起來
            if((newInterval.end >= itx.start && newInterval.end <= itx.end) || (newInterval.start <= itx.end && newInterval.start >= itx.start)){
                newInterval.start = Math.min(newInterval.start, itx.start);
                newInterval.end = Math.max(newInterval.end, itx.end);
            }
            // 將待合并Interval之后的存入一個(gè)列表中
            if(newInterval.end < itx.start){
                after.add(itx);
            }
        }
        // 把三部分加起來
        res.addAll(before);
        res.add(newInterval);
        res.addAll(after);
        return res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64554.html

相關(guān)文章

  • leetcode57. Insert Interval

    摘要：題目要求給定一組順序排列且相互之間沒有重疊的區(qū)間，輸入一個(gè)區(qū)間，將它插入到當(dāng)前的區(qū)間數(shù)組中，并且將需要合并的區(qū)間合并，之后返回插入并且合并后的區(qū)間。我們將這三個(gè)類型的區(qū)間分別標(biāo)注為類型，類型，類型。 題目要求 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge...

    Yuanf 評論0 收藏0

  • leetcode--57--Insert Interval

    摘要：問題描述分析這道題的關(guān)鍵在于理解問題，抽取原型，理解中間可以部分如何界定，以及非部分如何進(jìn)行追加。需要注意的是循環(huán)到最后一個(gè)元素和在最后一個(gè)元素的區(qū)別。 問題描述： Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You m...

    kycool 評論0 收藏0

  • leetcode56 Merge Intervals

    摘要：題目要求輸入一系列區(qū)間，將出現(xiàn)交叉的區(qū)間合并起來，并將合并后的區(qū)間返回。將這兩個(gè)數(shù)組分別排序可以得到和。也就是說，合并后的結(jié)果和是等價(jià)的。舉個(gè)栗子，輸入為，先判斷是否是獨(dú)立區(qū)間，可見可以和合并，則將修改為。 題目要求 Given a collection of intervals, merge all overlapping intervals. For example, Given...

    shmily 評論0 收藏0

  • [LeetCode] Insert Interval

    Problem Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times....

    Jonathan Shieber 評論0 收藏0

  • [LeetCode/LintCode] Merge Intervals

    摘要：方法上沒太多難點(diǎn)，先按所有區(qū)間的起點(diǎn)排序，然后用和兩個(gè)指針，如果有交集進(jìn)行操作，否則向后移動。由于要求的，就對原數(shù)組直接進(jìn)行操作了。時(shí)間復(fù)雜度是的時(shí)間。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

    gougoujiang 評論0 收藏0

發(fā)表評論

0條評論

antyiwei

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<