Come unire due array ordinati in Java

1. Introduzione

In questo tutorial, impareremo come unire due array ordinati in un singolo array ordinato.

2. Problema

Capiamo il problema. Abbiamo due array ordinati e vorremmo unirli in uno solo.

3. Algoritmo

Quando analizziamo il problema, è abbastanza facile osservare che possiamo risolvere questo problema utilizzando l'operazione di unione di Merge Sort.

Supponiamo di avere due array ordinati foo e bar di length fooLength e barLength , rispettivamente. Successivamente, possiamo dichiarare un altro array unito di dimensioni fooLength + barLength .

Dovremmo quindi attraversare entrambi gli array nello stesso loop. Manterremo un valore di indice corrente per ogni, fooPosition e barPosition . In una data iterazione del nostro ciclo, prendiamo qualsiasi array che abbia l'elemento di valore più piccolo nel loro indice e facciamo avanzare quell'indice. Questo elemento occuperà la posizione successiva nella matrice unita .

Infine, una volta trasferiti tutti gli elementi da un array, copieremo i rimanenti dall'altro nell'array unito .

Vediamo ora il processo in immagini per capire meglio l'algoritmo.

Passo 1:

Iniziamo confrontando gli elementi in entrambi gli array e scegliamo quello più piccolo.

Quindi incrementiamo la posizione nel primo array.

Passo 2:

Qui incrementiamo la posizione nel secondo array e passiamo all'elemento successivo che è 8.

Passaggio 3:

Alla fine di questa iterazione, abbiamo attraversato tutti gli elementi del primo array.

Passaggio 4:

In questo passaggio, copiamo semplicemente tutti gli elementi rimanenti dal secondo array al risultato .

4. Implementazione

Vediamo ora come implementarlo:

public static int[] merge(int[] foo, int[] bar) { int fooLength = foo.length; int barLength = bar.length; int[] merged = new int[fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while(fooPosition < fooLength && barPosition < barLength) { if (foo[fooPosition] < bar[barPosition]) { merged[mergedPosition++] = foo[fooPosition++]; } else { merged[mergedPosition++] = bar[barPosition++]; } } while (fooPosition < fooLength) { merged[mergedPosition++] = foo[fooPosition++]; } while (barPosition < barLength) { merged[mergedPosition++] = bar[barPosition++]; } return merged; }

E procediamo con un breve test:

@Test public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() { int[] foo = { 3, 7 }; int[] bar = { 4, 8, 11 }; int[] merged = { 3, 4, 7, 8, 11 }; assertArrayEquals(merged, SortedArrays.merge(foo, bar)); }

5. Complessità

Attraversiamo entrambi gli array e scegliamo l'elemento più piccolo. Alla fine, copiamo il resto degli elementi dal foo o dall'array bar . Quindi la complessità temporale diventa O (fooLength + barLength) . Abbiamo utilizzato un array ausiliario per ottenere il risultato. Quindi anche la complessità dello spazio è O (fooLength + barLength) .

6. Conclusione

In questo tutorial, abbiamo imparato come unire due array ordinati in uno solo.

Come al solito, il codice sorgente di questo tutorial può essere trovato su GitHub.