Как пересечь два отсортированных целочисленных массива без дубликатов?

Ответ 1

Эта проблема существенно сводится к операции объединения, а затем к операции фильтра (для удаления дубликатов и сохранения только внутренних совпадений).

Поскольку входы уже отсортированы, объединение может быть эффективно достигнуто с помощью merge join, с O (size (a) + size (б)).

Операция фильтра будет O (n), потому что вывод соединения сортируется и удаляет дубликаты, все, что вам нужно сделать, это проверить, является ли каждый элемент тем же, что и перед ним. Фильтрация только внутренних совпадений тривиальна, вы просто отбрасываете любые элементы, которые не были сопоставлены (внешние соединения).

Есть возможности для parallelism (как в соединении, так и в фильтре) для достижения лучшей производительности. Например, структура Apache Pig на Hadoop предлагает параллельную реализацию объединения объединения.

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

• Сравнение на основе сравнения - O (nlogn) - Относительно медленно, очень просто, используйте, если нет проблем с производительностью. Побеждает простота.

• Объединить соединение + Фильтр - O (n) - Быстро, подвержен ошибкам кодирования, используйте if производительность - проблема. В идеале старайтесь использовать существующую библиотеку для этого или, возможно, даже использовать базу данных, если это необходимо.

• Параллельная реализация - O (n/p) - Очень быстро, требует наличия другой инфраструктуры, используйте, если объем очень большой и ожидаемый рост, и это большая производительность узкое место.

(Также обратите внимание, что функция в вопросе intersectSortedArrays по существу является модифицированным объединенным объединением, в котором фильтр выполняется во время соединения. После этого вы можете фильтровать без потери производительности, хотя немного увеличенный объем памяти).

Заключительная мысль.

Фактически, я подозреваю, что большинство современных коммерческих СУБД предлагают потоки parallelism в их реализации объединений, поэтому то, что предлагает версия Hadoop, это машинный уровень parallelism (распространение). С точки зрения дизайна, возможно, хорошее, простое решение вопроса состоит в том, чтобы поместить данные в базу данных, индексировать по A и B (эффективно сортировать данные) и использовать внутреннее соединение SQL.

Ответ 2

Как насчет:

public static int[] intersectSortedArrays(int[] a, int[] b){
    int[] c = new int[Math.min(a.length, b.length)]; 
    int ai = 0, bi = 0, ci = 0;
    while (ai < a.length && bi < b.length) {
        if (a[ai] < b[bi]) {
            ai++;
        } else if (a[ai] > b[bi]) {
            bi++;
        } else {
            if (ci == 0 || a[ai] != c[ci - 1]) {
                c[ci++] = a[ai];
            }
            ai++; bi++;
        }
    }
    return Arrays.copyOfRange(c, 0, ci); 
}

Концептуально он похож на ваш, но содержит ряд упрощений.

Я не думаю, что вы можете улучшить временную сложность.

изменить: Я пробовал этот код, и он проходит все ваши модульные тесты.

Ответ 3

Использование arraylist для сохранения результата.

public ArrayList<Integer> arrayIntersection(int [] a, int[] b)
{
    int len_a=a.length;
    int len_b=b.length;
    int i=0;
    int j=0;
    ArrayList<Integer> alist=new ArrayList();

    while(i<len_a && j<len_b)
    {
        if(a[i]<b[j])
            i++;
        else if(a[i]>b[j])
            j++;
        else if(a[i]==b[j])
        {
            alist.add(a[i]);
            i++;
            j++;

        }
    }

   return alist;    
  }

Ответ 4

Если вы используете массивы Integer (object) и хотите использовать методы API java, вы можете проверить приведенный ниже код. Обратите внимание, что приведенный ниже код, вероятно, имеет большую сложность (поскольку он использует некоторую логику преобразования из одной структуры данных в другую) и потребление памяти (из-за использования объектов), чем примитивный метод, как указано выше. Я просто попробовал (пожимает плечами):

public class MergeCollections {
    public static void main(String[] args) {
        Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13};

        Set<Integer> intSet1 = new TreeSet<Integer>();
        intSet1.addAll(Arrays.asList(intArray1));
        intSet1.addAll(Arrays.asList(intArray2));
        System.out.println(intSet1);
    }
}

И вывод:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13]

Также проверьте эту ссылку: Algolist - Algo для объединения отсортированных массивов

РЕДАКТИРОВАТЬ: Изменен HashSet для TreeSet

EDIT 2: теперь, когда вопрос редактируется и очищается, я добавляю простое решение для поиска пересечения:

public class Intersection {
    public static void main(String[] args) {
        Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13};

        List<Integer> list1 = Arrays.asList(intArray1);
        Set<Integer> commonSet = new TreeSet<Integer>();
        for(Integer i: intArray2) {
            if(list1.contains(i)) {
                commonSet.add(i);
            }
        }

        System.out.println(commonSet);
    }
}

Ответ 5

Я не знаю, хорошо ли решить проблему таким образом:

say

  A,B are 1 based arrays
    A.length=m
    B.length=n

1) инициализировать массив, C, с длиной min (m, n)

2) сосредоточиться только на общей части, проверив первый и последний   элемент. здесь может использоваться двоичный поиск. возьмите пример, чтобы сохранить   несколько слов:

 A[11,13,15,18,20,28,29,80,90,100.........300,400]
    ^                                          ^
 B[3,4,5,6,7.8.9.10.12,14,16,18,20,..400.....9999]
                     ^                ^


then we need only focus  on

    A[start=1](11)-A[end=m](400)
    and
    B[start=9](12)-B[end](400)

3). сравните диапазон (end-start) обоих массивов. взяв массив с меньшим диапазоном, скажем A, для каждого элемента A[i] из A[start] ~ A[end], выполните двоичный поиск в B[start,end],

• если найдено, поместите элемент в C, reset B.start, чтобы найтиIdx + 1,

• в противном случае B.start устанавливается на наименьший элемент [j], который B [j] равен больше A [i], чтобы сузить диапазон

4) продолжить 3) до тех пор, пока все элементы в [начало, конец] не будут обработаны.

• на шаг 1, мы могли бы найти случай, если нет пересечения между два массива.
• при выполнении бинарного поиска на шаге 3 мы сравниваем A [i] с A [i-1], если то же, пропустите A [i]. для сохранения элементов в C уникальны.

таким образом, худший случай был бы lg (n!), если (A и B такие же)? не уверен.

Среднее значение?

Ответ 6

Здесь улучшается память:

Лучше сохранить ваши результаты (C) в динамической структуре, например, связанный список, и создать массив после того, как вы сделаете поиск пересекающихся элементов (точно так же, как вы делаете с массивом r). Этот метод был бы особенно хорош, если бы у вас были очень большие массивы для A и B и ожидалось, что общие элементы будут немного в сравнении (зачем искать огромный кусок смежной памяти, когда вам нужна только небольшая сумма?).

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