9

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

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

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

列表列表 B= {D, G, K, P, Z}

现在，显然 listB 在 listA 上也有 D 和 G，所以我希望 listA 是这样的

列表A = {A，B，C，E，F，H，I，J}

你们能否建议O（n）或小于O（n2）的解决方案。

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

4

4 回答 4

12

如果列表未排序，并且是 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-09T00:05:30.680 回答
3

您可以将两个列表元素添加到Set

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

于 2013-04-09T00:00:03.037 回答
0

就像 ssantos 回答的那样，您可以使用 Set。

或者，如果列表已排序，那么您可以交替地遍历它们。遍历 ListA 直到到达大于 ListB 的当前元素的元素，然后遍历 ListB 直到到达大于 ListA 的当前元素的元素，依此类推。

于 2013-04-09T00:02:34.767 回答
0

以下是在预期时间O(n)内解决的一些伪C。

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-09T01:25:44.743 回答