數據結構：唯一在名單

我有兩個列表，一個列表L1包含N1元素和另一個列表L2包含N2 elements.Both列表是不一樣的長度，幷包含重複elements.I要創造出具有獨特的元素另一個列表來自l1和l2。我可以如何有效地做到這一點，該解決方案的性能如何？數據結構：唯一在名單

P.S：我想要一個不使用任何其他數據結構的解決方案。

來源

2010-11-01 Jony

這功課嗎？聽起來像是這樣。 – 2010-11-01 17:17:31

每個列表是否包含可能重複的元素，或者您是否意味着列表之間可能存在重複？ – Jeff 2010-11-01 17:18:14

@Cameron：這是一個面試問題。 – Jony 2010-11-01 17:19:47

創建一個新的Set並從列表l1和l2中添加元素。最終集合將是不包含重複的集合。但要確保你已經正確實現了equals（）和hashCode（）。

下面是我的樣品（不完美）做同樣的。在這裏張貼它來驗證我的邏輯;-)或者看看是否有優化這個

Lit unique=... 


if(l1.size==l2.size()) 
{ 
    //o(n) 
    copyToUnique(l1, l2, unique) 
} 
else if(l1.size>l2.size()) 
{ 
    //o(n) + num of extra elements 
    copyToUnique(l1, l2, unique) 
    unique.addAll(l1.subList(l2.size(),l1.size()); 
} 
else if(l1.size<l2.size()) 
{ 
    //o(n) + num of extra elements 
    copyToUnique(l2, l1, unique) 
    unique.addAll(l2.subList(l1.size(),l2.size()); 
} 

public void copyToUnique(List l1, List l2, List unique) 
{ 
    for(Object element:l1) 
    { 
     if(!l2.contains(element)) 
     { 
      unique.add(element); 
     } 
    } 
unique.addAll(l2); 
}

來源

2010-11-01 17:16:36

+1擊敗了我。 – casablanca 2010-11-01 17:17:31

如果我不允許使用任何其他數據結構，該怎麼辦？ – Jony 2010-11-01 17:18:21

OP想要一個列表，而不是一個Set。 – dogbane 2010-11-01 17:18:29

如果您不能使用了一套更好的辦法，我認爲最好的辦法是做一個合併排序沒有重複。這個SO問題可能有所幫助：How do I use merge sort to delete duplicates?

來源

2010-11-01 17:29:59 Isac

如果您只需要使用列表，並且您有可能在每個列表和列表中重複列表，則需要創建一個新列表l3（用於保存l1和l2元素）並遍歷每個列表，如果對l3.contains（e）的調用返回false，則插入每個元素的e項。

正如其他人所說，使用一組絕對是刪除列表中的重複的項目最簡單的方法，並且列表可以從集創建返回給調用者。

性能是線性的，並基於l1 + l2中的元素數量。

來源

2010-11-01 17:30:29 Jeff

這個性能不是線性的，它是O（n^2），或類似的東西。你必須考慮檢查第三個列表是否包含元素。 – nojo 2010-11-01 17:33:12

這不會使它O（n^2）。它實際上取決於所使用的List實現，但包含來自SDK的實現的最壞情況將是線性的，我相信（ArrayList），並且插入將是最差情況的線性。所以，即使它不是一個直的O（n），那裏也有一個乘數和線性增長，而不是一個指數和二次增長。 – Jeff 2010-11-01 17:40:32

取決於l3是否排序。如果沒有排序，並假設沒有重複的最壞情況，則l3.contains（）將在一個遞增大小的列表上執行，從開始處的0比較開始執行到最後的N =（l1 + l2-1）比較： sum（0..N）= N *（N-1）/ 2。 – Lars 2010-11-01 17:57:16

的解決方案是O（nlogn）。將各排序列表，然後通過兩個列表一起走，找到重複。您可以根據哪個列表具有當前元素的「最小」值（或者它們是否相同）來增加一個列表或另一個列表（或兩者）的位置。這有一個合理的開銷，所以一些O（n^2）算法實際上可能會更快，這取決於數據的大小/分佈。

來源

2010-11-01 17:35:10 nojo

數據結構：唯一在名單

回答

相關問題