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

Question

我有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<Integer>首先从列表中创建一个.

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

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

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

之后,set将是两个列表的交集.

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

Answer 2

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

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