通过与另一个列表进行比较，从一个列表中删除重复项。

Question

我有两个对象列表，想要从一个列表中删除另一个列表中已经存在的实例。

例如：我有以下两个列表，假设每个字母代表一个对象。

List listA = {A, B, C , D, E, F, G, H , I , J}

List listB= {D, G, K, P, Z}

现在，很明显listB中有D和G，在listA中也有，所以我希望listA像这样：

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

你们能否建议一下用O（n）或小于O（n2）的复杂度解决这个问题。

我可以迭代两个列表并通过比较来删除重复实例，但我想要更有效率的方法。

- Pankaj Gadge

---

你能假设这些列表已经排序了吗？ - templatetypedef

No. Order doesnt matter! - Pankaj Gadge

有趣的是，第一个想法似乎总是排序，这当然非常合理，因为它允许线性复杂度的解决方案；但是一般来说，元素之间甚至不必存在偏序 :) - G. Bach

Answer 1

如果列表没有排序，并且是ArrayList或其他具有O(n)包含方法的类似列表实现，则应创建一个HashSet，其中包含listB的项目以执行删除操作。如果没有将项目放入set中，则最终性能为O(n^2)。

因此，完成您所需的最简单的方法是：

listA.removeAll(new HashSet(listB));

ArrayList.removeAll(Collection)在JDK 1.6和1.7版本中不会为您将项目放入集合中，这就是为什么您需要在上面自己创建一个HashSet的原因。

removeAll方法在遍历列表时将希望保留的项目复制到列表的开头，避免每次删除都进行数组压缩，因此使用它来对传入的HashSet执行操作是相当优化的，并且时间复杂度为O(n)。

- Trevor Freeman

---

这应该是一个被接受的答案。简洁而优雅。 - Dinesh

有趣！为什么不使用HashSet会导致O(n^2)的结果？我尝试搜索“数组压缩”，但无法从现有的解释中弄清楚... - DraxDomax

@DraxDomax O(n^2) 是因为 removeAll 方法通过迭代调用传入集合的 contains 方法来遍历被调用的列表。如果传入的集合是 ArrayList，则它具有 O(n) 的 contains 方法，这就是为什么我们最终得到 O(n^2) 的原因。现在，这并不完全准确，因为我们检查的集合可能具有有限的固定大小（例如 3 个元素或类似的大小），而不会随着另一个列表 N 的规模而扩展，所以它真正取决于您的使用情况。更准确的说法是它是 O(n * j)，其中 j 是传入集合的大小。 - Trevor Freeman

我认为如果更多的人注意到编写循环的影响，软件在现今的使用中会更加有效 :) 话虽如此，我可能没有工作，因为我不是那么擅长（尽管我在努力！）。感谢您的澄清!!! - DraxDomax

Answer 2

您可以将这两个列表元素添加到一个Set中。

要从一个列表中删除另一个列表的元素，请尝试listA.removeAll(listB);

- ssantos

---

通过将两个元素添加到SET中，我可以从列表中删除重复项。但是我想要完全从listA中删除它。 - Pankaj Gadge

Answer 3

以下是一些伪代码，以 期望时间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

- Arun

Answer 4

就像ssantos所回答的，你可以使用一个Set。

或者，如果这些列表是已排序的，那么你可以交替地迭代它们。迭代ListA直到你到达一个比ListB当前元素更大的元素，然后迭代ListB，直到你到达一个比ListA当前元素更大的元素，以此类推。

- Zim-Zam O'Pootertoot