通過與另一個列表比較從一個列表中刪除重複項

我有兩個對象列表，我想從其他列表中的一個列表中刪除實例。通過與另一個列表比較從一個列表中刪除重複項

例如我有以下兩個列表，並假設每個字母代表對象。

列表listA的= {A，B，C，d，E，F，G，H，I，J}

列表數組listB = {d，G，K，P，Z}

現在，顯然數組listB有d和G是有關於listA的太所以想要listA的是這樣

listA的= {A，B，C，E，F，H，I，J}

燦你們請提出一個解決方案，用O（n）或小於O（n2）來解決這個問題。

我可以遍歷這兩個列表並通過比較刪除重複的實例，但我想要更有效的東西。

來源

2013-04-08 Pankaj Gadge

你能假定列表已排序嗎？ – templatetypedef 2013-04-08 23:59:47

編號順序並不重要！ – 2013-04-09 00:02:03

有趣的是，第一個想法似乎總是排序，這當然是非常合理的，因爲它允許線性複雜度的解決方案;但是一般情況下，甚至不必在元素上存在偏序:) – 2013-04-09 00:12:18

你可以既列表元素添加到Set

要刪除一個列表上的元素從另一個嘗試listA.removeAll(listB);

來源

2013-04-09 00:00:03 ssantos

通過在SET中添加兩個元素，我可以從列表中刪除重複項。但我想完全從listA中刪除它。 – 2013-04-09 00:05:22

剛編輯我的回答:) – ssantos 2013-04-09 00:41:55

像ssantos回答，您可以使用一組。

或者，如果列表已排序，則可以交替遍歷它們。遍歷ListA，直到到達大於ListB當前元素的元素，然後迭代ListB，直到達到大於ListA當前元素的元素，等等。

來源

2013-04-09 00:02:34

如果列表未排序，並且是ArrayLists或其他類似的帶有O（n）包含方法的列表實現，那麼您應該創建一個帶有listB項目的HashSet以執行刪除操作。如果項目沒有放入一個集合，那麼你會以O（n^2）的性能結束。做你需要什麼

最簡單的方法是這樣的：

listA.removeAll(new HashSet(listB));

ArrayList.removeAll(Collection)不會把物品放入一組適合你（至少在JDK 1.6和我檢查1.7版本），這就是爲什麼你需要在上面自己創建HashSet。

removeAll方法會將您希望保留的項目複製到列表的開始位置，因爲它會遍歷它，從而避免數組壓縮每次移除，所以如圖所示針對傳入的HashSet使用它是相當理想的，並且是O（ N）。

來源

2013-04-09 00:05:30

以下是一些僞C在中解決的預計時間O(n)。

lenA = length pf listA 
lenB = length of listB 
shortList = (lenA <= lenB) ? A : B 
longList = (shortList == A) ? B : A 

create hash table hashTab with elements of shortList 

for each element e in longList: 
    is e present in hashTab: 
     remove e from longList 

now, longList contains the merged duplicate-free elements

來源

2013-04-09 01:25:44 Arun

通過與另一個列表比較從一個列表中刪除重複項

回答

相關問題