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

Question

我有 2 个整数列表，

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

我想找出其中的重复项，我有我通常的方法：-

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

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

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

Answer 1

当然 - 首先从列表之一创建一个 HashSet 。

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

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

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

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

请注意，如果您的两个列表一开始就已经排序，那么您的效率可能会更高。您只需同时迭代两者，将“光标”向前移动到当前具有较小值的迭代器。

Answer 2

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

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