Поиск общих элементов в двух массивах


Я только что этот вопрос в интервью. Я должен был написать некоторый код, чтобы найти все общие элементы в двух массивах. Это код, который я написал. Я мог только думать о 2-контур решение, но что-то мне подсказывает, что там должен быть способ сделать это с только 1 петля. Любые идеи?

public List<Integer> findCommonElements(int[] arr1, int[] arr2) {
    List<Integer> commonElements = new ArrayList<>();

    for (int i = 0; i < arr1.length; i++) {
        for (int j = 0; j < arr2.length; j++) {
            if (arr1[i] == arr2[j]) {
                commonElements.add(arr1[i]);
                break;
            }
        }
    }

    return commonElements;
}


Комментарии
3 ответа

Вы используете для поиска HashSet, это означает, что у вас есть 2 петли, но не вложенные. У вас есть логическое поиска HashSet в этом случае, когда все значения начинаются с ложного размера k где k (это обычно то, что используется в большом'notation) - это количество возможных целочисленных значений. Вы петли за ваш первый массив и для каждого значения вы идете hashset[firstArray[i]] = true; Как только вы сделали это, вы петлю над второй массив, собирается if(hashset[secondArray[i]]) commonElements.add(secondArray[i]);.

Это будет o(2Н), который затем становится просто о(п) за счет избавления от константы, ваше решение о(п^2). Хотя следует отметить, необходимое для хранения с помощью поиска HashSet значительно больше.

3
ответ дан 13 марта 2018 в 06:03 Источник Поделиться

Есть причина, почему "структуры данных и алгоритмы" имеет структуры данных часть добавлена, особенно первый. Причина того, почему структуры данных должны быть первое, что вы думаете о даже до написания какого-либо алгоритма.

Давайте спецификация код, который вы дали:


Написать некоторый код, чтобы найти все общие элементы в двух массивах.

Теперь первым делом-это во-первых, это не достаточно конкретными, что вы подразумеваете под "общие элементы", это включает повторяющиеся элементы так, например, [1,1,2] и [1,1,3] это будет [1,1] или просто [1]? Для этого я предполагаю, что вы имеете в виду элементы не повторяются.

Теперь после того как мы установили спецификации, которая является


Даны два массива чисел найти общих уникальных элементов.

Я бы сказал, что эти массивы будут звучать намного Как установить структуры данных, и этот набор данных структура, потому что мы хотим найти пересечение между этими двумя наборами. В Java это будет:

public static void main(String[] args) {
List<Integer> alist = Arrays.asList(new Integer[] {1,1,2});
List<Integer> blist = Arrays.asList(new Integer[] {1,1,3});

HashSet<Integer> aset = new HashSet<>(alist);
aset.retainAll(blist);

System.out.println(aset);
}

Это очень важно учитывать две вещи, когда кто-то дает вам спец, сначала продумывать это ясно, достаточно, а во-вторых, после того, как вы получили представление о том, что они хотят, нужно сильно подумать над структурой данных, поскольку они являются структурами, которые были опробованы и испытаны, чтобы быть эффективным на конкретные задачи.

В программе выше, пусть будет размер алист и B размер блист время сложность o(А + B), как это O(1) добавить элемент поиска HashSet, который мы делаем для каждого элемента, то нам петлю, хотя все элементы в B, потому что из retainAll функция должна делать содержит операции для каждого элемента, и что есть O(1) для поиска HashSet. Это намного эффективнее, чем o(АВ) ~ или о(N^2).

редактировать:

Благодаря nullbyte, отметив, что его более эффективным, чтобы сделать один для поиска HashSet и сделать ratainAll для всего, что единый набор. Приведенный выше код был скорректирован.

3
ответ дан 14 марта 2018 в 01:03 Источник Поделиться

Итак, смысл этого решения положить первый массив в хэш-набор, а затем проходят второй массив проверки, если элемент из второго массива присутствуют в наборе.

Это решение требует порядка o(n) времени и о(n) пространство, если массивы имеют одинаковую длину.

  public static List<Integer> findCommon(int[] a, int[] b) {
final Set<Integer> set = new HashSet<>(Arrays.stream(a).boxed().collect(Collectors.toList()));
final List<Integer> result = new LinkedList<>();
for (int element : b) {
if (set.contains(element)) {
result.add(element);
}
}
return result;
}

Или немного более лаконичное решение:

  public static List<Integer> findCommon(int[] a, int[] b) {
final Set<Integer> set = new HashSet<>(Arrays.stream(a).boxed().collect(Collectors.toList()));
set.retainAll(Arrays.stream(b).boxed().collect(Collectors.toList()));
return new ArrayList<>(set);
}

1
ответ дан 14 марта 2018 в 01:03 Источник Поделиться