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.
