1

Изучаю большую нотацию. Есть задача:

Дано два массива и надо найти общие элементы. Пример:

A[ ] = {4,2,5,6}

B[ ] = {3,7,6,9}

Надо, чтобы алгоритм нахождения был быстрее чем O(n^2).

Для решения данного вопроса надо написать программу и описать её принцип работы.

P.S. Написать алгоритм перебора легко, а вот как сделать так, чтобы это было быстрее O(n^2)?

edited:

Вариант решения:

import java.util.Arrays;

public class common {
    public int CommonElement(int a[], int b[]) {
        int aLen = a.length;
        int bLen = b.length;
        int[] c = new int[aLen+bLen];
        System.arraycopy(a, 0, c, 0, aLen);
        System.arraycopy(b, 0, c, aLen, bLen);
        Arrays.sort(c);


    for (int i = 0; i < c.length-1; i++) {
        if (c[i] == c[i+1]) {
            return c[i];
            }
    }
    return -1;



}


public static void main(String[] args) {
    int a[] = {4,2,5,6};
    int b[] = {3,6,8,9};
    common common = new common();
    System.out.println("answer = " + common.CommonElement(a, b));
} }
Дух сообщества
  • 1
Antonio112009
  • 2,631
  • 1
    Да как вариант - сложить вместе, отсортировать, посмотреть на те элементы, где подряд два одинаковых. Уже O(n*log n)... – Harry Feb 15 '18 at 06:55
  • @Harry вот я так как раз и думал. 1) a.add(b) 2) a.sort. 3) цикл нахождения стоящих рядом равных элементов. – Antonio112009 Feb 15 '18 at 06:56
  • @Harry но меня смущает sort. он тоже "жрет" скорость – Antonio112009 Feb 15 '18 at 06:57
  • Если же значения элементов представляют ограниченный список (как в примере - только цифры) - вообще сортировка подсчётом и O(n). Можно отсортировать один массив и искать элементы второго бинарным поиском - тоже будет O(n*log n). – Akina Feb 15 '18 at 06:57
  • Сортировка - O(n*log n), она, конечно, самое узкое место, но это узкое место - быстрее O(n^2), которого вы боялись :) – Harry Feb 15 '18 at 07:00
  • @Harry сейчас напишу решение (язык JAVA) – Antonio112009 Feb 15 '18 at 07:09
  • @Harry то есть такое решение оно будет меньше, чем O(n^2)? Если это меньше O(n^2), то тогда как посчитать тут O? – Antonio112009 Feb 15 '18 at 07:12
  • Неплохо было бы покидать ссылки на статьи, где можно прочитать про "нахождение" большого О. – Antonio112009 Feb 15 '18 at 07:12
  • Ну, лучше Кормена я не встречал, но он может показаться слишком академичным. Посмотрите весь список - https://ru.stackoverflow.com/questions/576507/%D0%9A%D0%BD%D0%B8%D0%B3%D0%B8-%D0%BF%D0%BE-%D1%82%D0%B5%D0%BC%D0%B5-%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B – Harry Feb 15 '18 at 11:44

2 Answers2

4

Два наброска вариантов.

Первый - сложить вместе, отсортировать, идти по отсортированному в поисках повторяющихся элементов.

Вариант второй - отсортировать каждый, а потом, как при сортировке слиянием, идти от меньших элементов, сравнивая элементы в обоих массивах. Не равны - там, где меньший, смещаем указатель на следующий. Если встречаются одинаковые - понятно :)

Если данные допускают, скажем, сортировку подсчетом - совсем просто: корзины, в которых больше одного элемента - это и есть совпадения. Тут вообще O(n).

Harry
  • 221,325
2

Поправьте, если ошибаюсь

Integer A[] = {4,2,5,6};
Integer B[] = {3,7,6,9};
Set<Integer> set = new HashSet<>();
set.addAll(Arrays.asList(A)); //O(n)
for (Integer b: B) {
  if (set.contains(b)) {
    System.out.println(b);
  }
} //O(n)
Александр Поташев
  • 735