摘要:題目要求輸入一系列區(qū)間,將出現(xiàn)交叉的區(qū)間合并起來,并將合并后的區(qū)間返回。將這兩個數(shù)組分別排序可以得到和。也就是說,合并后的結(jié)果和是等價的。舉個栗子,輸入為,先判斷是否是獨立區(qū)間,可見可以和合并,則將修改為。
題目要求
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].
輸入一系列區(qū)間,將出現(xiàn)交叉的區(qū)間合并起來,并將合并后的區(qū)間返回。這里需要注意的是,區(qū)間的大小順序無關(guān),即輸出為[1,2],[3,4]和[3,4],[1,2]都是可以的
思路一:簡單粗暴利用排序API第一次看到這道題目,難免就會想到,將這些區(qū)間按照開始值有小到大排序,然后依次比較前后兩個區(qū)間的開始值和結(jié)束值,如果出現(xiàn)重疊,則將兩個區(qū)間合并。
在這里先介紹一下,java中的兩種利用API進行排序的方法。
當(dāng)排序?qū)ο笫菙?shù)組時,可以使用Arrays.sort機制,它的核心實現(xiàn)在于Comparable接口。任何一個實現(xiàn)了該接口的數(shù)組中的成員都可以使用Arrays.sort方法。
當(dāng)排序?qū)ο笫羌蠒r,可以使用list.sort方法。它的核心實現(xiàn)在于Comparator接口。通過該接口可以實現(xiàn)集合的排序。
在這里不詳細(xì)介紹這二者的內(nèi)核和具體實現(xiàn),有興趣的可以查看java API。
代碼實現(xiàn)如下:
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; }
對對象的排序其實相當(dāng)?shù)挠绊懶屎托阅堋F鋵嵾@題的問題跳脫出來看,無需知道特定的區(qū)間,只要知道所有的按順序的起始值和終點值。
例如輸入為[1,3],[5,6],[2,7]
如果按照思路一,則需要先將對象排序,得出[1,3],[2,7],[5,6],然后再依次判斷是否需要合并臨近區(qū)間。
按照思路二,我們直接將區(qū)間看成起始值列表[1,5,2]和結(jié)束值列表[3,6,7]。將這兩個數(shù)組分別排序可以得到[1,2,5]和[3,6,7]。也就是說,[1,3],[5,6],[2,7]合并后的結(jié)果和[1,3],[2,6],[5,7]是等價的。
為什么呢?因為如果兩個區(qū)間重疊,那么這兩個區(qū)間的一個結(jié)束值和一個開始值必然不會出現(xiàn)在結(jié)果集中,也就是說,我只需要找到這兩個區(qū)間的一個最小值和一個最大值就可以了。如果是n個區(qū)間重疊,那么只要找這n個區(qū)間的最小值和最大值就可以了。同理,如果一個區(qū)間和任何一個區(qū)間都不會發(fā)生合并,它的開始值和結(jié)束值就必然會在排序后兩個數(shù)組中處于相同下標(biāo)的位置。且其結(jié)果值一定小于下一個下標(biāo)的開始值。
按照這種思路,實現(xiàn)的代碼如下:
public Listmerge2(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; }
可以看到,該算法的時間復(fù)雜度為O(4n)
思路三:無需排序的算法這個答案參考了一下高分回答。整理了一下思路如下:
其實在這里無需對各個區(qū)間排序。只需要將需要合并的區(qū)間合并起來即可。如果經(jīng)過判斷是獨立的區(qū)間,則將該區(qū)間加入結(jié)果集,如果不是獨立的區(qū)間,則將該區(qū)間合并至后續(xù)的區(qū)間并繼續(xù)判斷下一個區(qū)間在剩余的區(qū)間中是否是獨立的區(qū)間。
舉個栗子,輸入為[1,3],[5,6],[10,11],[2,7],
先判斷[1,3]是否是獨立區(qū)間,可見[1,3]可以和[2,7]合并,則將[2,7]修改為[1,7]。
接著判斷[5,6]是否可以合并至后面的區(qū)間,發(fā)現(xiàn)需要將[5,6]與[1,7]合并,合并為[1,7]。
最后,還剩下[10,11]和[1,7]可以先后加入結(jié)果集。
代碼如下:
public Listmerge3(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; }
想要了解更多開發(fā)技術(shù),面試教程以及互聯(lián)網(wǎng)公司內(nèi)推,歡迎關(guān)注我的微信公眾號!將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/70123.html
摘要:題目地址題目描述給出一個區(qū)間的集合,請合并所有重疊的區(qū)間。示例輸入輸出解釋區(qū)間和重疊將它們合并為示例輸入輸出解釋區(qū)間和可被視為重疊區(qū)間。解答按照區(qū)間起始節(jié)點排序。否則把列表最后一個區(qū)間和當(dāng)前區(qū)間合并。 題目地址:https://leetcode-cn.com/probl...題目描述:給出一個區(qū)間的集合,請合并所有重疊的區(qū)間。 示例 1: 輸入: [[1,3],[2,6],[8,10]...
摘要:方法上沒太多難點,先按所有區(qū)間的起點排序,然后用和兩個指針,如果有交集進行操作,否則向后移動。由于要求的,就對原數(shù)組直接進行操作了。時間復(fù)雜度是的時間。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...
摘要:我們只要把所有和該有重疊的合并到一起就行了。最后把前半部分的列表,合并后的大和后半部分的列表連起來,就是結(jié)果了。 Merge Intervals 最新更新請見 https://yanjia.me/zh/2019/02/... Given a collection of intervals, merge all overlapping intervals.For example, Gi...
摘要:問題描述分析這道題的關(guān)鍵在于理解問題,抽取原型,理解中間可以部分如何界定,以及非部分如何進行追加。需要注意的是循環(huán)到最后一個元素和在最后一個元素的區(qū)別。 問題描述: Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You m...
閱讀 4511·2021-09-22 14:57
閱讀 555·2019-08-30 15:56
閱讀 2658·2019-08-30 15:53
閱讀 2234·2019-08-29 14:15
閱讀 1684·2019-08-28 17:54
閱讀 553·2019-08-26 13:37
閱讀 3472·2019-08-26 10:57
閱讀 1041·2019-08-26 10:32