Наиболее эффективный способ возврата общих элементов из двух строковых массивов

Ответ 1

Редакция:

Это однострочный:

compareList.retainAll(new HashSet<String>(baseList));

retainAll impl (в AbstractCollection) выполняет итерацию по this и использует аргумент contains(). Включение аргумента в HashSet приведет к быстрому поиску, поэтому цикл внутри retainAll будет выполняться как можно быстрее.

Кроме того, имя baseList намекает на то, что оно является константой, поэтому вы получите значительное повышение производительности, если будете кэшировать это:

static final Set<String> BASE = Collections.unmodifiableSet(new HashSet<String>(Arrays.asList("one", "two", "three", "etc")));

static void retainCommonWithBase(Collection<String> strings) {
    strings.retainAll(BASE);
}

Если вы хотите сохранить исходный список, сделайте следующее:

static List<String> retainCommonWithBase(List<String> strings) {
   List<String> result = new ArrayList<String>(strings);
   result.retainAll(BASE);
   return result;
}

Ответ 2

Я бы использовал HashSets (и retainAll), что сделало бы всю проверку O (n) (для каждого элемента в поиск первого набора, если он существует (contains()), который является O (1) для HashSet). List быстрее создавать, хотя (HashSet, возможно, придется иметь дело с коллизиями...).

Имейте в виду, что Set и List имеют разную семантику (списки позволяют дублировать элементы, нули...).

Ответ 3

Сортируйте оба массива.

После сортировки вы можете выполнить итерацию обоих отсортированных массивов ровно один раз, используя два индекса.

Это будет O (NlogN).

Ответ 4

сохранить все не поддерживается списком. используйте вместо этого:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        String[] strings1={"a","b","b","c"},strings2={"b","c","c","d"};
        List<String> list=Arrays.asList(strings1);
        //list.retainAll(Arrays.asList(strings2)); // throws UnsupportedOperationException
        //System.out.println(list);
        Set<String> set=new LinkedHashSet<String>(Arrays.asList(strings1));
        set.retainAll(Arrays.asList(strings2));
        System.out.println(set);
    }
}

Ответ 5

То, что вы хотите, называется пересечением. Видеть, что: Пересечение и объединение ArrayLists в Java

Использование коллекции на основе Hash обеспечивает действительно более быстрый метод contains(), особенно для строк, которые имеют оптимизированный хэш-код.

Если вы можете импортировать библиотеки, вы можете рассмотреть возможность использования Sets.intersection из Guava.

Edit:

Не знаю о методе keepAll.

Обратите внимание, что реализация AbstractCollection, которая, кажется, не переоценивается для HashSets и LinkedHashSets:

public boolean retainAll (сборник c) {      boolean modified = false;      Итератор it = iterator();      while (it.hasNext()) {          if (! c.contains(it.next())) {              it.remove();              modified = true;          }      }      возврат изменен;  }

Это означает, что вы вызываете contains() в параметре коллекции! Это означает, что если вы передадите параметр List, у вас будет равный вызов по многим элементам списка, для каждой итерации!

Вот почему я не думаю, что приведенные выше реализации с использованием saveAll хороши.

public <T> List<T> intersection(List<T> list1, List<T> list2) {
    boolean firstIsBigger = list1.size() > list2.size();
    List<T> big =  firstIsBigger ? list1:list2;
    Set<T> small =  firstIsBigger ? new HashSet<T>(list2) : new HashSet<T>(list1);
    return big.retainsAll(small)
}

Выбор использования Set для наименьшего списка, потому что он быстрее конкретизирует набор, а большой список выполняет итерацию довольно хорошо...

Обратите внимание, что один из параметров исходного списка может быть изменен, вам нужно сделать копию...

Ответ 6

У меня было интервью, и этот вопрос был вопросом, который они задавали мне во время технического интервью. Мой ответ был следующим строкам кода:

public static void main(String[] args) {

        String[] temp1 = {"a", "b", "c"};
        String[] temp2 = {"c", "d", "a", "e", "f"};
        String[] temp3 = {"b", "c", "a", "a", "f"};

        ArrayList<String> list1 = new ArrayList<String>(Arrays.asList(temp1));
        System.out.println("list1: " + list1);
        ArrayList<String> list2 = new ArrayList<String>(Arrays.asList(temp2));
        System.out.println("list2: " + list2);
        ArrayList<String> list3 = new ArrayList<String>(Arrays.asList(temp3));
        System.out.println("list3: " + list3);

        list1.retainAll(list2);
        list1.retainAll(list3);
        for (String str : list1)
            System.out.println("Commons: " + str);
}

Вывод:

list1: [a, b, c]
list2: [c, d, a, e, f]
list3: [b, c, a, a, f]
Commons: a
Commons: c