java - 通过与另一个列表比较从一个列表中删除重复项

Question

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

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

列表 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) 的解决方案。

我可以遍历两个列表并通过比较删除重复的实例，但我想要更高效的方法。

Answer 1

如果列表未排序，并且是 ArrayLists 或其他具有 O(n) contains 方法的类似列表实现，那么您应该使用 listB 的项目创建一个 HashSet 以执行删除。如果这些项目没有放入集合中，那么您最终将获得 O(n^2) 的性能。

因此，执行所需操作的最简单方法是:

listA.removeAll(new HashSet(listB));

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

removeAll 方法会在遍历列表时将您希望保留的项目复制到列表的开头，避免每次删除时压缩数组，因此如图所示，针对传入的 HashSet 使用它是合理的最佳选择，时间复杂度为 O(n ).