streamalism.org

1. Introduktion

I denne vejledning skal vi lære at flette to sorterede arrays i et enkelt sorteret array.

2. Problem

Lad os forstå problemet. Vi har to sorterede arrays, og vi vil gerne flette dem til en.

3. Algoritme

Når vi analyserer problemet, det er ret let at observere, at vi kan løse dette problem ved at bruge fletteoperationen af ​​Merge Sort.

Lad os sige, at vi har to sorterede arrays foo og bar længde fooLength og barLængde, henholdsvis. Dernæst kan vi erklære et andet array fusioneret af størrelse fooLength + barLength.

Vi skal derefter krydse begge arrays i samme loop. Vi opretholder en aktuel indeksværdi for hver, fooPosition og barPosition. På en given iteration af vores løkke, vi tager, hvilken matrix der har elementet med mindre værdi ved deres indeks, og fremfører dette indeks. Dette element indtager den næste position i fusioneret array.

Endelig, når vi har overført alle elementer fra en matrix, kopierer vi de resterende fra den anden til den fusioneret array.

Lad os nu se processen i billeder for bedre at forstå algoritmen.

Trin 1:

Vi starter med at sammenligne elementerne i begge arrays, og vi vælger den mindre.

Derefter øges vi positionen i først array.

Trin 2:

Her øger vi positionen i sekund array og gå videre til det næste element, som er 8.

Trin 3:

I slutningen af ​​denne iteration har vi krydset alle elementerne i først array.

Trin 4:

I dette trin kopierer vi bare alle de resterende elementer fra sekund array til resultat.

4. Implementering

Lad os nu se, hvordan du implementerer det:

offentlig statisk int [] fletning (int [] foo, int [] bar) {int fooLength = foo.length; int barLength = bar.length; int [] flettet = ny int [fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; mens (fooPosition <fooLength && barPosition <barLength) {hvis (foo [fooPosition] <bar [barPosition]) {fusioneret [mergedPosition ++] = foo [fooPosition ++]; } andet {fusioneret [mergedPosition ++] = bar [barPosition ++]; }} mens (fooPosition <fooLength) {fusioneret [mergedPosition ++] = foo [fooPosition ++]; } mens (barPosition <barLength) {fusioneret [mergedPosition ++] = bar [barPosition ++]; } returneret flettet }

Og lad os fortsætte med en kort test:

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

5. Kompleksitet

Vi krydser begge arrays og vælger det mindre element. I sidste ende kopierer vi resten af ​​elementerne fra foo eller den bar array. Så tidskompleksiteten bliver O (fooLength + barLength). Vi har brugt et hjælpearray til at opnå resultatet. Så rumkompleksiteten er også O (fooLength + barLength).

6. Konklusion

I denne vejledning lærte vi, hvordan man fletter to sorterede arrays til en.

Som normalt kan kildekoden til denne tutorial findes på GitHub.