Самый быстрый способ объединить уникальные целые числа из 2 массивов

Question

Если у меня есть 2 массива:

arr1 = {9,8}
arr2 = {13,12,10,9,8}

Я бы хотел получить:

{13,12,10}

И учитывая массивы:

arr1 = {23,22,21,20,19,18,17,16}
arr2 = {21,17}

результат будет:

{23,22,20,19,18,16}

Таким образом, в основном я получаю числа, которые находятся либо в arr1, либо в arr2, но не в обоих.

• 2 массива могут быть разной длины.
• 2 массива отсортированы в порядке убывания, и конечный массив также должен иметь это свойство.
• Это делается миллионы раз, поэтому я пытаюсь уменьшить / предотвратить распределение объектовкак можно лучше.Вот почему я не использую наборы для работы.

Answer 1

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

9 8 7 5
     6 4 3 2

например. 9,8,7 можно взять непосредственно из массива 1, тогда средняя часть нуждается в большей заботе, тогда вы можете взять 4,3,2 непосредственно из массива 2. Было бы полезно узнать, являются ли непересекающиеся части ваших входов может быть значимым или нет.

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

Вам понадобится массив для результатов - один из подходов состоит в том, чтобы выделить массив, достаточно большой, чтобы вместить оба входных массива, в худшем случае, а затем либо сделать System.arrayCopy() в новом массиве правильного размера, или просто вести подсчет количества фактических элементов. Другой подход заключается в использовании ArrayList и выполнении toarray впоследствии, если это необходимо.

Answer 2

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

1. сравнить первый элемент из каждого массива
2. если неравенство, добавьте больший к уникальному набору
3. иначе удалите оба элемента
4. если вы достигли конца одного массива, добавьте все элементы, оставшиеся в другом массиве, в уникальный набор

, который является жадным O (n) решением. Вот реализация, слегка протестированная: D

/**
 * Returns the sorted EXOR of two sorted int arrays (descending). Uses
 * arrays, index management, and System.arraycopy.
 * @author paislee
 */
int[] arrExor(int[] a1, int[] a2) {

    // eventual result, intermediate (oversized) result
    int[] exor, exor_builder = new int[a1.length + a2.length];
    int exor_i = 0; // the growing size of exor set

    int a1_i = 0, a2_i = 0; // input indices
    int a1_curr, a2_curr; // elements we're comparing

    // chew both input arrays, greedily populating exor_builder
    while (a1_i < a1.length && a2_i < a2.length) {

        a1_curr = a1[a1_i];
        a2_curr = a2[a2_i];

        if (a1_curr != a2_curr) {
            if (a1_curr > a2_curr)
                exor_builder[exor_i++] = a1[a1_i++];
            else
                exor_builder[exor_i++] = a2[a2_i++];
        } else {
            a1_i++;
            a2_i++;
        }        
    }

    // copy remainder into exor_builder
    int[] left = null; // alias for the unfinished input
    int left_i = 0, left_sz = 0; // index alias, # elements left

    if (a1_i < a1.length) {
        left = a1;
        left_i = a1_i;
    } else {
        left = a2;
        left_i = a2_i;
    }

    left_sz = left.length - left_i;
    System.arraycopy(left, left_i, exor_builder, exor_i, left_sz);
    exor_i += left_sz;

    // shrinkwrap and deliver
    exor = new int[exor_i];
    System.arraycopy(exor_builder, 0, exor, 0, exor_i);
    return exor;
}

Answer 3

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

http://en.wikipedia.org/wiki/Merge_sort

Поскольку у вас есть две отсортированные коллекции, объединение O (n)

Answer 4

Используйте наборы, но используйте их повторно и очищайте их в начале каждой итерации. ИЛИ, поскольку массивы гарантированно сортируются, вы можете использовать что-то сравнимое с объединением. (Поддерживайте индекс в обоих массивах. На каждом шаге, если 2 индекса указывают на равные элементы, перемещайте индексы за этими элементами и ничего не добавляйте в выходные данные. В противном случае добавьте элемент большего размера в выходные данные и увеличить только этот индекс.)