streamalism.org

1. Introduksjon

I denne opplæringen skal vi lære å slå sammen to sorterte matriser i en enkelt sortert matrise.

2. Problem

La oss forstå problemet. Vi har to sorterte matriser, og vi vil gjerne slå dem sammen.

3. Algoritme

Når vi analyserer problemet, det er ganske enkelt å observere at vi kan løse dette problemet ved å bruke fletteoperasjonen til Merge Sort.

La oss si at vi har to sorterte matriser foo og bar av lengde fooLength og barLengde, henholdsvis. Deretter kan vi erklære en annen matrise slått sammen av størrelse fooLength + barLength.

Vi skal da krysse begge matriser i samme sløyfe. Vi opprettholder en nåværende indeksverdi for hver, fooPosisjon og barPosisjon. På en gitt iterasjon av løkken vår, vi tar hvilken matrise som har elementet med mindre verdi i indeksen, og fremmer indeksen. Dette elementet vil innta neste posisjon i slått sammen array.

Til slutt, når vi har overført alle elementene fra den ene matrisen, kopierer vi de resterende fra den andre til slått sammen array.

La oss nå se prosessen i bilder for å bedre forstå algoritmen.

Trinn 1:

Vi begynner med å sammenligne elementene i begge gruppene, og vi velger den mindre.

Deretter øker vi posisjonen i først array.

Steg 2:

Her øker vi posisjonen i sekund array og gå videre til neste element som er 8.

Trinn 3:

På slutten av denne iterasjonen har vi krysset alle elementene i først array.

Trinn 4:

I dette trinnet kopierer vi bare alle gjenværende elementer fra sekund array til resultat.

4. Gjennomføring

La oss nå se hvordan du implementerer det:

offentlig statisk int [] flette (int [] foo, int [] bar) {int fooLength = foo.length; int barLength = bar.length; int [] fusjonert = ny int [fooLength + barLength]; int fooPosisjon, barPosisjon, sammenslåttPosisjon; fooPosition = barPosition = fusjonertPosisjon = 0; mens (fooPosition <fooLength && barPosition <barLength) {if (foo [fooPosition] <bar [barPosition]) {flettet [fusjonertPosisjon ++] = foo [fooPosisjon ++]; } annet {fusjonert [fusjonertPosisjon ++] = bar [barPosisjon ++]; }} mens (fooPosition <fooLength) {flettet [fusjonertPosisjon ++] = foo [fooPosisjon ++]; } mens (barPosition <barLength) {slått sammen [mergedPosition ++] = bar [barPosisjon ++]; } returnert flettet; }

Og la oss fortsette med en kort test:

@Test offentlig ugyldighet givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray () {int [] foo = {3, 7}; int [] bar = {4, 8, 11}; int [] flettet = {3, 4, 7, 8, 11}; assertArrayEquals (slått sammen, SortedArrays.merge (foo, bar)); }

5. Kompleksitet

Vi krysser begge gruppene og velger det mindre elementet. Til slutt kopierer vi resten av elementene fra foo eller bar array. Så tidskompleksiteten blir O (fooLength + barLength). Vi har brukt et hjelpearrangement for å oppnå resultatet. Så romkompleksiteten er også O (fooLength + barLength).

6. Konklusjon

I denne opplæringen lærte vi hvordan vi kan slå sammen to sorterte matriser i en.

Som vanlig kan kildekoden for denne opplæringen bli funnet på GitHub.