leetcode56之合併區間
題目描述：
給出一個區間的集合，請合併所有重疊的區間。
示例：
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區間 [1,3] 和 [2,6] 重疊, 將它們合併為 [1,6]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區間 [1,3] 和 [2,6] 重疊, 將它們合併為 [1,6]
代碼如下：
1 def merge(intervals): 2 ''' 3 4 :param intervals: 5 :return 6 ''' 7 # 根據區間左端點排序 8 intervals.sort(key=lambda x: x[0]) 9 if intervals: 10 res = [intervals[0]] 11 else: 12 return intervals 13 for i in range(1, len(intervals)): 14 # 可以合併 15 if (intervals[i][-1] - intervals[i][0] + res[-1][-1] - res[-1][0]) \ 16 >= intervals[i][-1] - res[-1][0]: 17 res[-1] = [res[-1][0], max(intervals[i][-1], res[-1][-1])] 18 # 不能合併,將intervals當前值放入res中 19 else: 20 res.append(intervals[i]) 21 22 return res 23 24 25 print('--------測試merge()---------') 26 A = [[1, 2], [0, 6], [7, 9], [10, 18]] 27 B = [] 28 res = merge(B) 29 print("res=", res) 30 31 32 def merge1(intervals): 33 ''' 34 35 :param intervals: 36 :return: 37 ''' 38 intervals.sort(key=lambda x: x[0]) 39 res = [] 40 for item in intervals: 41 # 如果res為空 42 if not res: 43 res.append(item) 44 else: 45 # 可以合併 46 if item[0] <= res[-1][1]: 47 res[-1][1] = max(item[1], res[-1][1]) 48 # 不能合併 49 else: 50 res.append(item) 51 52 return res 53 54 55 print("=============測試merge1()==============") 56 result = merge1(A) 57 print("result=", result)
輸出：
--------測試merge()--------- res= [] =============測試merge1()============== result= [[0, 6], [7, 9], [10, 18]]
一點思考：
本題在解答過程中重點考察了二維數組索引求值。另外一點，當遇到循環比較數組（列表）前後兩元素數值時，可以定義一個空的列表，用來動態存放數組中另一個待比較元素，這樣實現起來更方便。當放入第一個元素時，採用方法二明顯更方便一點，值得借鑒。方法一稍顯得麻煩一點。
