эффективный способ сделать «содержит» между двумя списками

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

Обычный способ - добавить каждый элемент из первого списка в HashSet, а затем проверить каждый элемент во втором списке на наличие в этом наборе:

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