資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究合併 Python 中的區間
假設我們有一組區間，我們必須合併所有重疊的區間。因此，如果區間為 [[1,3], [2,6], [8,10], [15,18]]，則合併後的區間為 [[1,6],[8,10],[15,18]]。這是因為有兩個重疊的區間，區間為 [1,3] 和 [2,6]，它們被合併為 [1,6]
我們看看這些步驟 −
- 如果區間列表長度為 0，則返回一個空白列表
- 使用快速排序機制對區間列表進行排序
- stack := 一個空棧，並將 intervals[0] 插入棧中
- 對於 i 介於 1 到區間長度 - 1
- last_element := 棧的頂層元素
- 如果 last_element 的結束 >= intervals[i] 的第一個元素，則
- last_element 的結束 = intervals[i] 的結束和 last_element 的結束的最大值
- 從棧中彈出一個元素
- 將 last_element 壓入棧中
- 否則將 intervals[i] 壓入棧中
- 返回棧
我們看看以下實現，以加深理解 −
範例
class Solution(object): def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ if len(intervals) == 0: return [] self.quicksort(intervals,0,len(intervals)-1) #for i in intervals: #print(i.start, i.end) stack = [] stack.append(intervals[0]) for i in range(1,len(intervals)): last_element= stack[len(stack)-1] if last_element[1] >= intervals[i][0]: last_element[1] = max(intervals[i][1],last_element[1]) stack.pop(len(stack)-1) stack.append(last_element) else: stack.append(intervals[i]) return stack def partition(self,array,start,end): pivot_index = start for i in range(start,end): if array[i][0]<=array[end][0]: array[i],array[pivot_index] =array[pivot_index],array[i] pivot_index+=1 array[end],array[pivot_index] =array[pivot_index],array[end] return pivot_index def quicksort(self,array,start,end): if start<end: partition_index = self.partition(array,start,end) self.quicksort(array,start,partition_index-1) self.quicksort(array, partition_index + 1, end) ob1 = Solution() print(ob1.merge([[1,3],[2,6],[8,10],[15,18]]))
輸入
[[1,3],[2,6],[8,10],[15,18]]
輸出
[[1, 6], [8, 10], [15, 18]]
更新於:2020年5月4日
1千次觀看
廣告