Java在O中合併了2個集合（1）

我需要能夠將2個大集合合併爲1。哪種集合類型最適合我？我不需要隨機訪問各個元素。通常我會去找一個鏈表，但是我無法將Java中的兩個鏈表與O（1）的運行時合併起來，這可以用許多其他語言來完成，因爲我必須將每個元素複製到新列表中。Java在O中合併了2個集合（1）

編輯：謝謝你的答案。你的回答都非常有幫助，我設法完成了這項工作。下次我將使用自己的鏈接列表來實現。

來源

2011-12-03 Tiddo

排序列表的懶惰合併是如何發聲的？可以在O（1）中構建合併結果，併爲列表上的每個操作添加一個已攤銷的O（1），直到實際評估爲止。 – 2011-12-03 14:05:02

你可以自己實現一個LinkedList，但是LinkedList可以自己吸引大量時間。 – bestsss

'我無法將Java中的2個鏈表與O（1）'的運行時合併，這顯然不是真的。如果您使用Java實現自己的鏈接列表，則可以將Java中的2個鏈接列表與O（1）的運行時合併。該語句僅適用於標準庫實現，因此您的語句可能應該是「我不能將2 java.util.LinkedList與O（1）的運行時合併」。 –

您可以創建在O級聯Iterable視圖（1）使用的Guava的Iterables.concat方法之一：

Iterable<T> combined = Iterables.concat(list1, list2);

這將允許您遍歷兩個列表上的所有元素，而不復制一個對象任何元素。

來源

2011-12-03 14:28:23 ColinD

從理論上講，您可以合併2個鏈表在O（1），因爲所有你需要做的是點一次的最後一個節點到第二的第一個節點（假設你有這些參考資料）。

集合的addAll方法似乎暗示O（n）的運行時間，因爲他們都在談論迭代器。細節可能是JVM具體...

我不認爲有將在O（n）的組合任意集合。你可能不得不推出自己的。

來源

2011-12-03 13:58:47 hvgotcodes

我認爲問題是如何在Java中做到這一點。因此，他可以像任何其他集合一樣處理最終結果，而無需創建自己的類。 +1這個問題btw –

我知道，但正如揚說的，我想知道這是否已經可以在Java本身。 – Tiddo

最後一個假設是否真的在Java中成立？ – 2011-12-03 14:02:58

這裏最簡單的解決方案確實是列表清單。意味着你需要一些簡單的包裝函數，但沒有什麼複雜的。

來源

2011-12-03 14:01:57 Voo

這可能是一個解決方案，我要試試這個 – Tiddo

雖然這個問題有點老，我必須爲此解決方案添加一條評論：在我的具體情況中，我開始使用僅包含一個元素的集合，並且在某些情況下需要將其合併到一起，直到只剩下一個列表。但是，如果您使用列表技術列表，您將創建一個非常深層次的列表，因此這不會非常有效。因此，這個解決方案只有在列表不經常合併時纔有效。 – Tiddo

我覺得你最好的最好的是創建列表的實現，這需要名單>作爲參數，然後委託。換句話說，有一個列表清單，並將它們連接起來作爲一個列表。當你走過去列表1中的元素，你開始看錶2.

出於某種原因，我認爲番石榴有過這樣的名單。但我無法在他們的javadoc中找到它。

來源

2011-12-03 14:07:59 yshavit

並且由於它實現了標準的List接口，所以可以在其他代碼中使用它。 +1 –

合併鏈表確實O（1），並且可以考慮基於陣列的列表以同樣的方式，即具有連接之間的多個對象[]。

有上面的實現，當從中間/開始移除/插入時，它比ArrayList快。迭代實際上是一樣的。隨機訪問可能會稍微慢一些。

來源

2011-12-03 14:14:01 bestsss

我想建議從apache.commons的CompositeCollection類，但看看source code這也運行在O（n）。如果您只需要迭代元素並且不想按照ColinD的建議使用Google Collections，那麼您可以輕鬆創建自己的複合迭代器，例如，

public class CompositeCollectionIterator<T> implements Iterator<T>{ 

    private Iterator<T>[] iterators; 
    private int currentIteratorIndex = 0; 
    public CompositeCollectionIterator(Collection<T>... aCollections) { 
    iterators = new Iterator[ aCollections.length]; 
    for (int i = 0, aCollectionsLength = aCollections.length; i < aCollectionsLength; i++) { 
     Collection<T> collection = aCollections[ i ]; 
     iterators[i] = collection.iterator(); 
    } 
    } 

    public boolean hasNext() { 
    if (iterators[currentIteratorIndex].hasNext()) return true; 
    else if (currentIteratorIndex < iterators.length - 1){ 
     currentIteratorIndex++; 
     return hasNext(); 
    } 
    return false; 
    } 

    public T next() { 
    return iterators[currentIteratorIndex].next(); 
    } 

    public void remove() { 
    iterators[currentIteratorIndex].remove(); 
    } 
}

來源

2011-12-03 14:36:07 Robin

如果只是希望有對象的集合，爲O合併它們（1）時間，並且不介意實現你自己的數據結構，那麼要做到這一點最簡單的方法是使用不平衡的二叉樹：每個節點既可以是一個葉（存儲一個值），也可以是兩棵樹的組合，您可以將它們作爲兩個具有抽象超類或接口的類來實現。深度優先遍歷可以用來提取元素。

這與ColinD對迭代器連接的建議基本相同，但是更加簡單。

美中不足的是，遍歷這個集合將不是O（ ñ）！它將爲O（ n + m）其中 m是您執行的合併數（因爲每個合併都是要遍歷的節點）。我的解決方案和ColinD都是如此。我不知道對於這個問題的所有可能的解決方案是否屬實。

沒關係上述。在這種方案下，每一次合併都至少添加一個元素，因此m < n等迭代成本仍然爲O（n）。（如果你使用迭代器串聯，確保你不經常串聯空迭代器，因爲這將增加成本。）

來源

2011-12-03 19:55:50

通過使用兩個鏈表爲您的藏品，並存儲指向的第一和最後一個元素每個列表（在添加/刪除項目時都可能需要更新這兩個指針），您可以將兩個列表合併到O（1）中 - 只需將第一個列表的最後一個元素連接到第二個列表的第一個元素，然後調整第一個/最後一個指針。

恐怕你需要在Java中自己實現鏈表，因爲你沒有直接訪問LinkedList的底層節點，因此你不能直接連接最後一個元素第一個列表到第二個列表的第一個元素。

幸運的是，在Java中很容易找到鏈表實現，因爲它是數據結構課程中非常常見的主題。例如，here是一個 - 我知道，名稱是西班牙文，但ListaEncadenada（「LinkedList」）和NodoLista（「ListNode」）中的代碼非常簡單，應該不言自明，最重要的是 - 實現包含指向列表的第一個和最後一個元素，並且可以很容易地修改以適合您的需求。

來源

2011-12-04 01:39:37

Java在O中合併了2個集合（1）

回答

相關問題