быстрый способ объединить уникальные целые числа от 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

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

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

который является greedy 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 2

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

Answer 3

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

9 8 7 5 
    6 4 3 2 

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

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

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

Answer 4

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

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

Поскольку у вас есть два отсортированных коллекций, слияние О (п)