有效的方式做到'包含'两个列表 [英] efficient way to do 'contains' between two lists

问题描述

我有整数2列出，

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!");
  } 
}

我听说包含（）是 O（N），使我实施为O（n ^ 2）。

有没有更好的方式来做到这一点，（小于为O（n ^ 2））？

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

推荐答案

当然 - 创建一个的HashSet＆LT;整数GT; 从列表中的一个第一

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!");
    }
}

如果你想找到的所有重复条目，你甚至都不需要编写自己的循环，如设置＆LT; E＆GT; 为您提供所需要的一切...

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));

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

请注意，如果同时你的列表已经排序开始与你甚至可以比这更有效。你只需在同一时间迭代两者，移动光标前进的任何迭代器目前拥有较小的值。

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屋！