Как пересечь два отсортированных целочисленных массива без дубликатов? - PullRequest
12 голосов
/ 10 февраля 2012

Это вопрос интервью, который я использую в качестве упражнения на программирование.

Ввод: Два отсортированных целочисленных массива A и B в порядке возрастания и разных размеров N и M соответственно

Вывод: Сортированный целочисленный массив C в порядке возрастания, содержащий элементы, которые отображаются как в A, так и в B

Ограничения: Дублирование не допускаетсяв C

Пример: Для ввода A = {3,6,8,9} и B = {4,5,6,9,10,11}, вывод должен бытьC = {6,9}

Спасибо за ваши ответы, все!Подводя итог, можно сказать, что есть два основных подхода к этой проблеме:

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

Другой способ, которым мы могли бы сделать это, состоит в том, чтобы сканировать один из массивов линейно, используя двоичный файл.поиск, чтобы найти совпадение во втором массиве.Это будет означать время O (N * log (M)), если мы сканируем A и для каждого из его N элементов выполняется двоичный поиск по времени B (O (log (M))).

Я реализовалоба подхода и провели эксперимент, чтобы увидеть, как эти два сравниваются (подробности об этом можно найти здесь ).Метод бинарного поиска, кажется, выигрывает, когда M примерно в 70 раз больше, чем N, когда N содержит 1 миллион элементов.

Ответы [ 6 ]

6 голосов
/ 10 февраля 2012

Как насчет:

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); 
}

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

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

edit: Я пробовал этот код, и он проходит все ваши юнит-тесты.

5 голосов
/ 11 февраля 2012

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

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

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

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

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

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

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

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

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

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

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

3 голосов
/ 12 февраля 2012

Использование 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;    
  }
0 голосов
/ 11 февраля 2012

Вот улучшение памяти:

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

РЕДАКТИРОВАТЬ: еще одна вещь, которую я хотел бы изменить, и это могло бы быть немного придирчивым, это то, что я бы избегал использования несвязанных циклов, когда наихудшее число итераций известно заранее.

0 голосов
/ 11 февраля 2012

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

скажем

  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, сбросить B.start в foundIdx + 1,

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

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

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

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

Средний случай?

0 голосов
/ 10 февраля 2012

Если вы используете массивы 'Integer' (объект) и хотите использовать методы 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

РЕДАКТИРОВАТЬ 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);
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...