合併列表中的重疊項目

我的目標是合併以下示例列表中的重疊元組。合併列表中的重疊項目

如果一個項目落在下一個範圍內，這兩個元組將不得不合並。得到的元組覆蓋了兩個項目的範圍（最小值到最大值）。例如; [(1,6),(2,5)]將導致[(1,6)]，作爲[2,5]落在[(1,6)]

mylist=[(1, 1), (1, 6), (2, 5), (4, 4), (9, 10)]

的範圍內我嘗試：

c=[] 
t2=[] 
for i, x in enumerate(mylist): 
    w=x,mylist[i-1] 
    if x[0]-my[i-1][1]<=1: 
     d=min([x[0] for x in w]),max([x[1] for x in w]) 
     c.append(d) 
for i, x in enumerate(set(c)): 
    t=x,c[i-1] 
    if x[0]-c[i-1][1]<=1: 
     t1=min([x[0] for x in t]),max([x[1] for x in t]) 
     t2.append(t1) 
print sorted(set(t2))

派生的輸出：

[(1, 6), (1, 10)]

希望的輸出：

[(1, 6), (9, 10)]

有關如何獲得所需輸出的任何建議（如果可能，請在更少的行中）？謝謝。

來源

2014-03-27 Tiger1

你的問題還不清楚。請重新說明 – sshashank124

合併和重疊的標準是什麼？仍然不清楚 – sshashank124

如果其中一個輸入是'（3,7）'，應該輸出什麼？ – thefourtheye

可以解決O（nlogn）這個問題

首先，你需要通過它的起點您的時間間隔進行排序。之後，您將創建一個新的堆棧，併爲每個時間間隔執行以下操作：

如果它爲空，只需按當前時間間隔（如果不是），則檢查堆棧中的第一個時間間隔是否與當前時間間隔重疊。如果確實如此，則彈出它，並將其與當前時間間隔合併，並將結果推回。如果不這樣做，那麼只需按下當前的時間間隔即可。檢查完所有間隔後，您的堆棧將包含所有合併間隔。

來源

2014-03-27 07:06:00 Valera

只是示範它並讓我們看到輸出。 – Tiger1

我不能在python中編寫代碼，但你所要求的是一個非常着名的算法問題，可以通過這個算法來解決。我希望你的Python知識允許你實現它，因爲沒有太複雜的東西 – Valera

@ m.wasowski O（NlogN）+ O（N）？ – thefourtheye

基礎上回答@Valera，Python實現：

mylist=[(1, 6), (2, 5), (1, 1), (3, 7), (4, 4), (9, 10)] 

result = [] 
for item in sorted(mylist): 
    result = result or [item] 
    if item[0] > result[-1][1]: 
     result.append(item) 
    else: 
     old = result[-1] 
     result[-1] = (old[0], max(old[1], item[1])) 

print result # [(1, 7), (9, 10)]

來源

2014-03-27 07:27:07

感謝您的解決方案。 – Tiger1

合併列表中的重疊項目

回答

相關問題