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

Question

我有两个对象列表,我想从其他列表中的一个列表中删除实例.

例如,我有两个列表,并假设每个字母代表对象.

列表a = {A,B,C,D,E,F,G,H,I,J}

列表清单B = {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).

Answer 2

您可以将两个列表元素添加到集合中

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