每天一道leetcode56-合併區間

考試結束，班級平均分只拿到了年級第二，班主任於是問道:大家都知道世界第一高峰珠穆朗瑪峰，有人知道世界第二高峰是什麼嗎？正當班主任要繼續發話，只聽到角落默默想起來一個聲音:」K2」

前言

2018.11.13號打卡
明天的題目：
https://leetcode-cn.com/problems/minimum-path-sum/descrip

題目

每天一道leetcode56-合併區間
分類：數組
中文連結：
https://leetcode-cn.com/problems/merge-intervals/description/
英文連結
https://leetcode.com/problems/merge-intervals/description/

題目詳述

給出一個區間的集合，請合併所有重疊的區間。
示例 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] 可被視為重疊區間。

題目詳解

思路

首先根據數組中的第一個數字進行排序，[1,3][2,6][8,10]中的就是1,2,8根據這三個數字對二維數組中進行排序

排完序以後，這樣二維數組中的數組就按照第一個數字的大小進行了排序，所以第一個數字是依次遞增的

然後就去比較[1,3]中3與下一個數組中2和6比較大小，如果數字3在2和6之間說明這兩個數組是可以合併的；合併完是[1,6]

[1,6]繼續與[8,10]合併，比較6與8,10，6是小於8的所以這個時候不能合併，只能二維數組的下標i進行i++的操作

這個還有一種情況就是比如是[1,10]與[2,8],10是大於8的這個時候，也可以進行合併

把這三種情況討論一遍進行

代碼

1class Interval {
2      int start;
3      int end;
4      Interval() { start = 0; end = 0; }
5      Interval(int s, int e) { start = s; end = e; }
6  }
7
8
9public List<Interval> merge(List<Interval> intervals) {
10    Collections.sort(intervals, new Comparator<Interval>() {
11        @Override
12        public int compare(Interval o1, Interval o2) {
13            if(o1.start > o2.start)
14                return 1;
15            else if(o1.start < o2.start)
16                return  -1;
17            else
18                return 0;
19        }
20    });
21    int i = 0;
22    while(i < intervals.size())
23    {
24        if(i != intervals.size() - 1)
25        {
26            if(intervals.get(i).end >= intervals.get(i+1).start && intervals.get(i).end <= intervals.get(i+1).end)
27            {
28                int tempStart = intervals.get(i).start;
29                int tempEnd = intervals.get(i+1).end;
30                intervals.remove(i);
31                intervals.get(i).start = tempStart;
32                intervals.get(i).end = tempEnd;
33            }else if(intervals.get(i).end < intervals.get(i+1).start){
34                i++;
35            }else if(intervals.get(i).end > intervals.get(i+1).end){
36                intervals.remove(i+1);
37                i=i;
38            }
39        }else {
40            i++;
41        }
42    }
43    return intervals;
44}

代碼講解

10-20行就是根據第一個數字來進行排序

26行-32行就是去比較 [1,3] [2,6]（分別代表intervals.get(i) 和intervals.get(i+1)）中3滿足了>=2 且 <= 6 然後就進行合併

33-34行就是[1,3] [5,7]中3 < 5了無法進行合併，i++

35-37行就是[1,10] [2,8] 中 10大於8也可以合併 （看到這裡，你可能會有疑問為啥可以合併了，因為我們在10-20行已經根據第一個數字排序過了，所以前後兩個數組中[a,3],[b,7]比如說這個，a是必然小於等於b的）

39-40行，最後一個元素，直接i++

結束語

2018.11.13號打卡

作者喬戈裡親歷2019秋招，哈工大計算機本碩，百度準入職java工程師，歡迎大家關注我的微信公眾號：程式設計師喬戈裡，公眾號有3T編程資源，以及我和我朋友（準入職百度C++工程師）在秋招期間整理的近200M的面試必考的java與C++面經，並有每天一道leetcode打卡群與技術交流群，歡迎關注。

幫戳文末的 獷高 相當於打賞2毛