什麼是兩個排序列表交集的最快算法？

說，有兩個已排序的列表：A和B.什麼是兩個排序列表交集的最快算法？

所述的條目和B的數量可以變化。（它們可以很小/很大，它們可以相互類似/顯着不同）。

什麼是已知的功能最快的算法？

任何人都可以給我一個想法或參考嗎？

來源

2016-11-10 syko

可以在O（n日誌（n））的通過將在列表二進制搜索在列表B.所有元素如果列表的大小有很大的不同然後優選在較大的列表中搜索執行它。 – Shubham

看來你的方法很糟糕。你爲什麼要問最快的已知算法，而不是開發你自己的算法，而不會採取不必要的步驟？ – xenteros

@syko我給你下面的工作代碼 – xenteros

假設A具有m元素而B具有n元素，其中m ≥ n。信息從理論上說，我們所能做的最好是

(m + n)! 
lg -------- = n lg (m/n) + O(n) 
    m! n!

比較，因爲爲了驗證一個空的交集，我們實際上需要進行排序的合併。通過遍歷B並保持A中的「光標」指示應該插入B最近元素以維持排序順序的位置，我們可以通過迭代B獲得該範圍的常數因子。我們使用exponential search使光標前進，因爲這是的

lg x_1 + lg x_2 + ... + lg x_n,

的順序，其中x_1 + x_2 + ... + x_n = m + n是m一些整數分區上的總成本。這筆款項是O(n lg (m/n))的凹陷lg。

來源

2016-11-10 22:30:33

假設有2名名單A和B的整數

for(int i = A.size() - 1; i > -1; --i){ 
    Integer currentInteger = A.get(i); 
    if(!B.remove(currentInteger)) 
     A.remove(currentInteger); 
}

來源

2016-11-10 12:32:32 Roxy

我不知道這是最快的選項，但這裏有一個在O(n+m)運行，其中n和m您的列表的大小：

遍歷兩個列表，直到其中一人是通過以下方式空：
事先一一列表。
在另一個列表上前進，直到找到等於或大於其他列表的當前值的值。
如果相等，元素所屬的交集，你可以將其追加到另一個列表
如果是大於其他因素，推進其他名單上，直到找到比這個值以上的值
如說，重複此，直到其中一個列表爲空

來源

2016-11-10 12:36:41 Keiwan

這是自然的，甚至可能是最佳的*鏈接*名單（其中線性掃描將是不可避免的）。另一方面，如果隨機訪問是可能的（如在Python列表中，它們確實是數組），那麼使用二進制搜索來查找下一個公共元素的東西可能會更好，當列表很大並且交叉點很小時可能會更好。如果不瞭解更多關於清單的信息，似乎很難說最好的方法是什麼。 –

@JohnColeman這是正確的。我的答案是基於這樣的假設OP在談論不受陣列支持內部鏈表（如Java的ArrayList的或陣列/在許多其他編程語言列表），這樣訪問元素不可能在O（1）。 – Keiwan

什麼是已知此功能的最快的算法？

使用merge sort技術，它是最好的，當兩個列表是分類。需要O(n+m)才能獲得組合的排序列表。

沒有辦法可以排序兩個列表而無需遍歷每個列表。所以你能達到的最好的是O(n+m)。

怎麼做：有兩份名單的頭開始，比較和皮卡的較低值，逐漸移動到捐助列表中的下一個，重複，直到一個或兩個列表爲空。如果一個列表保持非空，只需將其附加到結果列表中。

來源

2016-11-10 12:52:32

對問題的假設是列表已經排序。如果一個列表由100個奇數組成，另一個列表由1000000000個偶數組成，那麼它不應該花費1,000,000,100步來確定它們的交集是空的，所以我懷疑'O（m + n）'是最優的。 –

問題是你將如何使用鏈表中的隨機訪問，再加上你很少會事先知道列表的數字或模式的類型。那麼，這不是一個不適用於列表的情景嗎？ –

OP對鏈接列表和非鏈接列表沒有明確說明。如果這些隨機訪問列表，你知道它們的大小，最好的可能是1 3的算法之間進行選擇，這取決於M + N'，'M *的log（n，2）'和'N *日誌的' （m，2）'是最小的。 100次基體2的對數是1000000100小於3000，這是數量級比1000000100小几個數量級，以便這些尺寸的簡單合併的方法是不能作爲在較大的列表中的100種元素的連續二進制搜索一樣好。如果正確實施，最初的搜索將停止，最終答案是交叉點是空的。 –

什麼是兩個排序列表交集的最快算法？

回答

相關問題