java 通过与另一个列表进行比较从一个列表中删除重复项
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15891076/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Removing duplicates from one list by comparing with another list
提问by Pankaj Gadge
I have a two lists of objects and I would like to remove the instances from one list which is there in other list.
我有两个对象列表，我想从另一个列表中的一个列表中删除实例。
e.g. I have following two lists and suppose each letter represents the object.
例如，我有以下两个列表，并假设每个字母代表对象。
List listA = {A, B, C , D, E, F, G, H , I , J}
列表 listA = {A、B、C、D、E、F、G、H、I、J}
List listB= {D, G, K, P, Z}
列表 listB= {D, G, K, P, Z}
Now, clearly listB has D and G which are there on listA too so I want listA to be like this
现在，很明显 listB 有 D 和 G，它们也在 listA 上，所以我希望 listA 像这样
listA = {A, B, C , E, F, H , I , J}
listA = {A, B, C , E, F, H , I , J}
Can you guys please suggest what would be the solution for this with O(n) or less than O(n2).
你们能建议使用 O(n) 或小于 O(n2) 的解决方案吗？
I can iterate over both the lists and remove the duplicate instances by comparing but I want to have something more efficient.
我可以遍历两个列表并通过比较删除重复的实例，但我想要更有效的东西。
回答by Trevor Freeman
If the lists are unsorted, and are ArrayLists or other similar list implementations with an O(n) contains method, then you should create a HashSet with the items of listB in order to perform the removal. If the items are not put into a set then you will end up with O(n^2) performance.
如果列表未排序，并且是 ArrayLists 或其他具有 O(n) contains 方法的类似列表实现，那么您应该使用 listB 的项目创建一个 HashSet 以执行删除。如果这些项目没有放入一个集合中，那么你最终会得到 O(n^2) 的性能。
Easiest way to do what you need is thus:
做你需要的最简单的方法是：
listA.removeAll(new HashSet(listB));
ArrayList.removeAll(Collection)will not put the items into a set for you (at least in the JDK 1.6 and 1.7 versions I checked), which is why you need to create the HashSet yourself in the above.
ArrayList.removeAll(Collection)不会为您将项目放入集合中（至少在我检查的 JDK 1.6 和 1.7 版本中），这就是您需要在上面自己创建 HashSet 的原因。
The removeAll method will copy the items you wish to keep into the beginning of the list as it traverses it, avoiding array compacting with each removal, so using it against a passed in HashSet as shown is reasonably optimal and is O(n).
removeAll 方法将在遍历列表时将您希望保留的项目复制到列表的开头，避免每次删除时对数组进行压缩，因此对传入的 HashSet 使用它（如图所示）是合理的最佳选择，并且是 O(n)。
回答by ssantos
回答by Zim-Zam O'Pootertoot
Like ssantos answered, you can use a Set.
就像 ssantos 回答的那样，您可以使用 Set。
Alternatively, if the lists are sorted, then you can alternately iterate through them. Iterate through ListA until you reach an element that is greater than the current element of ListB, then iterate through ListB until you reach an element that is greater than the current element of ListA, etc.
或者，如果列表已排序，则您可以交替遍历它们。遍历 ListA 直到找到一个大于 ListB 的当前元素的元素，然后遍历 ListB 直到找到一个大于 ListA 的当前元素的元素，以此类推。
回答by Arun
Following is some pseudo-C to solve in expected time O(n).
以下是一些伪-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
