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

資訊專欄INFORMATION COLUMN

[LeetCode/LintCode] Merge Intervals

gougoujiang / 1903人閱讀

摘要：方法上沒太多難點，先按所有區(qū)間的起點排序，然后用和兩個指針，如果有交集進(jìn)行操作，否則向后移動。由于要求的，就對原數(shù)組直接進(jìn)行操作了。時間復(fù)雜度是的時間。

Problem

Given a collection of intervals, merge all overlapping intervals.

Example 
Given intervals => merged intervals:

[                     [
  [1, 3],               [1, 6],
  [2, 6],      =>       [8, 10],
  [8, 10],              [15, 18]
  [15, 18]            ]
]
Challenge 
O(n log n) time and O(1) extra space.
Note

方法上沒太多難點，先按所有區(qū)間的起點排序，然后用pre和cur兩個指針，如果有交集進(jìn)行merge操作，否則pre向后移動。由于要求O(1)的space，就對原數(shù)組直接進(jìn)行操作了。
時間復(fù)雜度O(nlogn)是Collections.sort()的時間。for循環(huán)是O(n)。
這道題有兩個點：
學(xué)會使用Collections.sort(object, new Comparator(){})進(jìn)行排序;
對于要進(jìn)行更改的數(shù)組而言，其一，for循環(huán)不要用for (a: A)的形式，會出現(xiàn)ConcurrentModificationException的編譯錯誤，文檔是這樣解釋的：it is not generally permissible for one thread to modify a Collection while another thread is iterating over it. 其二，對intervals的cur元素進(jìn)行刪除操作之后，對應(yīng)的index i要減去1。

Solution Update 2018-9 
class Solution {
    public List merge(List intervals) {
        if (intervals == null || intervals.size() < 2) return intervals;
        intervals.sort((i1, i2) -> i1.start-i2.start);
        List res = new ArrayList<>();
        int start = intervals.get(0).start, end = intervals.get(0).end; //use two variables to maintain prev bounds
        for (Interval interval: intervals) {                            //iterate the interval list
            if (interval.start > end) {                                 //if current interval not overlapping with prev:
                res.add(new Interval(start, end));                      //1. add prev to result list
                start = interval.start;                                 //2. update prev bounds
                end = interval.end;
            }
            else end = Math.max(end, interval.end);                     //else just update prev end bound
        }
        res.add(new Interval(start, end));                              //add the prev which was updated by the last interval
        return res;
    }
}
in-place
class Solution {
    public List merge(List intervals) {
        if (intervals == null || intervals.size() < 2) return intervals;
        intervals.sort((i1, i2) -> i1.start-i2.start);
        Interval pre = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.start > pre.end) pre = cur;
            else {
                pre.end = Math.max(pre.end, cur.end);
                intervals.remove(cur);
                i--;
            }
        }
        return intervals;
    }
}

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

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

相關(guān)文章

  • [Leetcode] Merge Intervals and Insert Interval 合并間

    摘要：我們只要把所有和該有重疊的合并到一起就行了。最后把前半部分的列表，合并后的大和后半部分的列表連起來，就是結(jié)果了。 Merge Intervals 最新更新請見 https://yanjia.me/zh/2019/02/... Given a collection of intervals, merge all overlapping intervals.For example, Gi...

    antyiwei 評論0 收藏0

  • 【LC總結(jié)】Intervals題目 (Insert/Merge/Number of Airplane

    摘要：忘了這題怎么做，汗顏無地。邊界用記錄每個時刻的飛行數(shù)目。對于某一時刻，起飛和降落同時發(fā)生，只計算一次。先強勢插入，再 Merge Intervals Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals: ...

    Achilles 評論0 收藏0

  • leetcode56 Merge Intervals

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

    shmily 評論0 收藏0

  • [LeetCode/LintCode] Top K Frequent Words

    LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

    0x584a 評論0 收藏0

  • leetcode--57--Insert Interval

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

    kycool 評論0 收藏0

發(fā)表評論

0條評論

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