在两个列表之间进行“包含”的有效方法

我有2个整数列表，

l1 = new ArrayList(); l2 = new ArrayList(); 

我想找出两者中的重复项目，我有我惯常的做法： –

 for (Integer i : l1) { if(l2.contains(i)){ System.out.println("Found!"); } } 

我听说contains()是O(n) ，使我的实现O(n^2) 。

有没有更好的方法来做到这一点，（少于O(n^2) ）？

Answer 1

当然 – 首先从其中一个列表创建一个HashSet 。

 Set set = new HashSet(l2); for (Integer i : l1) { if (set.contains(i)) { System.out.println("Found!"); } } 

如果你想找到所有重复的条目，你甚至不需要编写自己的循环，因为Set提供了你需要的一切……

 Set set = new HashSet(l2); set.retainAll(new HashSet(l1)); 

之后， set将是两个列表的交集。

请注意，如果两个列表都已经排序，您可以比这更有效。 您只需同时迭代两者，向前移动“光标”，以便任何迭代器当前具有较小的值。

Answer 2

通常的方法是将第一个列表中的每个项目添加到HashSet ，然后测试第二个列表中的每个项目是否存在于该集合中：

 Set firstSet = new HashSet(l1); for (Integer i : l2) { if (firstSet.contains(i)) { // Do stuff } }