資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中的區間列表交集
假設我們有兩個封閉區間列表，這裡每個區間列表都是成對不相交且已排序的。我們需要找到這兩個區間列表的交集。
我們知道封閉區間[a, b]表示為 a <= b，即實數集 x 滿足 a <= x <= b。兩個封閉區間的交集是一個實數集，它要麼為空，要麼可以表示為一個封閉區間。
因此，如果輸入類似於 A = [[0,2],[5,10],[13,23],[24,25]] 和 B = [[1,5],[8,12],[15,24],[25,27]]，則輸出將為 [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]。
為了解決這個問題，我們將遵循以下步驟：
建立一個列表 res，設定 I := 0 和 j := 0
定義一個名為 intersect() 的方法，它將接收 a 和 b：
如果 a[0] <= b[0] 且 a[1] >= b[0]，則返回 true；
否則，如果 b[0] <= a[0] 且 b[1] >= a[0]，則返回 true；否則返回 false。
當 I < A 的大小 且 j < B 的大小 時
如果 intersect(A[i], B[j])
temp := A[i, 0]、B[j, 0] 的最大值，A[i,1] 和 B[j, 1] 的最小值
A[i,0] := temp[1] + 1, B[j,0] := temp[1] + 1
如果 A[i,0] > A[i,1] 或 A[i,1] <= temp[0]，則將 i 加 1
如果 B[j,0] > B[j,1] 或 B[j,1] <= temp[0]，則將 j 加 1
result.append(temp)
跳過下一次迭代
如果 A[i,0] > B[j, 1]，則將 j 加 1，否則將 i 加 1
讓我們看看下面的實現以更好地理解：
示例
class Solution(object): def intervalIntersection(self, A, B): result = [] i,j = 0,0 while i < len(A) and j < len(B): if self.intersect(A[i],B[j]): temp = [max(A[i][0],B[j][0]),min(A[i][1],B[j][1])] A[i][0]=temp[1]+1 B[j][0] = temp[1]+1 if A[i][0] > A[i][1] or A[i][1] <= temp[0]: i+=1 if B[j][0]>B[j][1] or B[j][1] <= temp[0]: j+=1 result.append(temp) continue if A[i][0]>B[j][1]: j+=1 else: i+=1 return result def intersect(self,a,b): if a[0]<=b[0] and a[1]>=b[0]: return True if b[0]<=a[0] and b[1] >=a[0]: return True return False ob = Solution() print(ob.intervalIntersection([[0,2],[5,10],[13,23],[24,25]],[[1,5],[8,12],[15,24],[25,27]]))
輸入
[[0,2],[5,10],[13,23],[24,25]] [[1,5],[8,12],[15,24],[25,27]]
輸出
[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]
230 次檢視
