Kako spojiti dva razvrstana niza u Javi

1. Uvod

U ovom uputstvu naučit ćemo kako spojiti dva sortirana polja u jedan sortirani niz.

2. Problem

Razumijemo problem. Imamo dva razvrstana niza i željeli bismo ih spojiti u jedan.

3. Algoritam

Kada analiziramo problem, prilično je lako primijetiti da taj problem možemo riješiti pomoću operacije spajanja sortiranja spajanja.

Recimo da imamo dva razvrstana niza foo i bar duljine fooLength i šipkaDužina, odnosno. Dalje, možemo deklarirati još jedan niz spojene veličine fooLength + barLength.

Tada bismo trebali preći oba niza u istoj petlji. Zadržat ćemo trenutnu vrijednost indeksa za svaku, fooPosition i barPosition. Na zadanoj iteraciji naše petlje, uzmemo koji god niz ima element manje vrijednosti u svom indeksu i taj indeks unaprijedimo. Ovaj će element zauzeti sljedeću poziciju u spojene niz.

Konačno, nakon što prenesemo sve elemente iz jednog polja, kopirat ćemo preostale iz drugog u spojene niz.

Pogledajmo sada postupak na slikama kako bismo bolje razumjeli algoritam.

Korak 1:

Počinjemo s usporedbom elemenata u oba polja, a mi odabiremo manji.

Zatim povećavamo položaj u prvi niz.

Korak 2:

Ovdje povećavamo položaj u drugi niz i prijeđite na sljedeći element koji je 8.

Korak 3:

Na kraju ove iteracije prešli smo sve elemente prvi niz.

Korak 4:

U ovom koraku samo kopiramo sve preostale elemente iz drugi niz do proizlaziti.

4. Provedba

Sada da vidimo kako to primijeniti:

javna statička int [] spajanje (int [] foo, int [] bar) {int fooLength = foo.length; int barLength = bar.length; int [] spojeno = novo 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 {spojeno [mergedPosition ++] = bar [barPosition ++]; }} while (fooPosition <fooLength) {merged [mergedPosition ++] = foo [fooPosition ++]; } while (barPosition <barLength) {merged [mergedPosition ++] = bar [barPosition ++]; } povratak spojen; }

I nastavimo s kratkim testom:

@Test javna praznina givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray () {int [] foo = {3, 7}; int [] traka = {4, 8, 11}; int [] spojeno = {3, 4, 7, 8, 11}; assertArrayEquals (spojeno, SortedArrays.merge (foo, bar)); }

5. Složenost

Prelazimo oba niza i biramo manji element. Na kraju kopiramo ostatak elemenata iz foo ili bar niz. Dakle, vremenska složenost postaje O (fooLength + barLength). Za dobivanje rezultata koristili smo pomoćni niz. Dakle, i složenost prostora je O (fooLength + barLength).

6. Zaključak

U ovom uputstvu naučili smo kako spojiti dva sortirana niza u jedan.

Kao i obično, izvorni kod za ovu lekciju možete pronaći na GitHubu.