在两个列表之间执行“包含"的有效方法 [英] efficient way to do 'contains' between two lists

问题描述

我有 2 个整数列表，

I have 2 lists of integers,

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

我想找出它们两个中重复的项目，我有我常用的方法:-

I want to find out duplicate items in both of them, I have my usual approach:-

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

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

I've heard contains() is O(n), making my implementation O(n^2).

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

Is there a better way to do this, (less than O(n^2)) ?

推荐答案

当然 - 首先从其中一个列表中创建一个 HashSet.

Sure - create a HashSet<Integer> from one of the lists first.

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

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

If you want to find all duplicate entries, you don't even need to write your own loop, as Set<E> provides everything you need...

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

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

Afterwards, set will be the intersection of the two lists.

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

Note that you can be even more efficient than this if both your lists are already sorted to start with. You just iterate over both at the same time, moving the "cursor" forward for whichever iterator currently has the smaller value.

这篇关于在两个列表之间执行“包含"的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！