streamalism.org

1. Introduksjon

I denne artikkelen vil vi se hvordan du gjør det Finn kdet minste elementet i foreningen av to sorterte matriser.

Først definerer vi det nøyaktige problemet. For det andre ser vi to ineffektive, men greie løsninger. For det tredje skal vi se på en effektiv løsning basert på et binært søk på de to matriser. Til slutt vil vi se på noen tester for å bekrefte at algoritmen vår fungerer.

Vi ser også Java-kodebiter for alle deler av algoritmen. For enkelhets skyld vil implementeringen vår bare fungere på heltall. Imidlertid fungerer den beskrevne algoritmen med alle datatyper som er sammenlignbare og til og med kan implementeres ved hjelp av Generics.

2. Hva er KDet minste elementet i Union of Two Sorted Arrays?

2.1. De Kdet minste elementet

For å finne kdet minste elementet, også kalt kth-order statistikk, i en matrise, bruker vi vanligvis en valgalgoritme. Imidlertid opererer disse algoritmene på en enkelt usortert matrise, mens vi i denne artikkelen vil finne kdet minste elementet i to sorterte matriser.

Før vi ser flere løsninger på problemet, la oss nøyaktig definere hva vi ønsker å oppnå. For det, la oss hoppe rett inn i et eksempel.

Vi får to sorterte matriser (en og b), som ikke nødvendigvis trenger å ha like mange elementer:

I disse to gruppene ønsker vi å finne kdet minste elementet. Mer spesifikt ønsker vi å finne kdet minste elementet i den kombinerte og sorterte matrisen:

Den kombinerte og sorterte matrisen for vårt eksempel er vist i (c). De Første minste element er 3, og 4. plass minste element er 20.

2.2. Dupliserte verdier

Vi må også definere hvordan du skal håndtere dupliserte verdier. Et element kan forekomme mer enn en gang i en av gruppene (element 3 i rekke en) og forekommer også igjen i den andre matrisen (b).

Hvis vi bare teller duplikater en gang, teller vi som vist i (c). Hvis vi teller alle forekomster av et element, teller vi som vist i (d).

I den resterende delen av denne artikkelen vil vi telle duplikater som vist i (d), og dermed telle dem som om de var forskjellige elementer.

3. To enkle, men mindre effektive tilnærminger

3.1. Bli med og sorter deretter de to matriser

Den enkleste måten å finne kDet minste elementet er å bli med i matriser, sortere dem og returnere kdet elementet i den resulterende matrisen:

int getKthElementSorted (int [] list1, int [] list2, int k) {int length1 = list1.length, length2 = list2.length; int [] combinedArray = new int [lengde1 + lengde2]; System.arraycopy (liste1, 0, combinedArray, 0, liste1.lengde); System.arraycopy (list2, 0, combinedArray, list1.length, list2.length); Arrays.sort (combinedArray); retur kombinertArray [k-1]; }

Med n er lengden på den første matrisen og m lengden på den andre matrisen, får vi den kombinerte lengden c = n + m.

Siden kompleksiteten for sorten er O (c log c), er den generelle kompleksiteten i denne tilnærmingen O (n log n).

En ulempe ved denne tilnærmingen er at vi trenger å lage en kopi av matrisen, noe som resulterer i mer nødvendig plass.

3.2. Slå sammen de to arrangementene

I likhet med ett trinn i Merge Sort-sorteringsalgoritmen, kan vi slå sammen de to matriser og deretter direkte hente kelementet.

Grunnideen til sammenslåingsalgoritmen er å starte med to pekere, som peker på de første elementene i første og andre matrise (a).

Vi sammenligner deretter de to elementene (3 og 4) ved pekerne, legg til den mindre (3) til resultatet, og flytt pekeren en posisjon fremover (b). Igjen sammenligner vi elementene i pekepinnene og legger til den mindre (4) til resultatet.

Vi fortsetter på samme måte til alle elementene blir lagt til den resulterende matrisen. Hvis en av inngangsarrayene ikke har flere elementer, kopierer vi ganske enkelt alle de gjenværende elementene i den andre inngangsgruppen til resultatmatrisen.

Vi kan forbedre ytelsen hvis vi ikke kopierer hele matriser, men stopper når den resulterende matrisen har k elementer. Vi trenger ikke engang å lage en ekstra matrise for den kombinerte matrisen, men kan bare operere på de originale matriser.

Her er en implementering i Java:

offentlig statisk int getKthElementMerge (int [] liste1, int [] liste2, int k) {int i1 = 0, i2 = 0; mens (i1 <list1.length && i2 <list2.length && (i1 + i2) <k) {if (list1 [i1] <list2 [i2]) {i1 ++; } annet {i2 ++; }} hvis ((i1 + i2) <k) {return i1 0 && i2> 0) {return Math.max (list1 [i1-1], list2 [i2-1]); } annet {return i1 == 0? liste2 [i2-1]: liste1 [i1-1]; }}

Det er enkelt å forstå tidskompleksiteten til denne algoritmen er O (k). En fordel med denne algoritmen er at den lett kan tilpasses for å vurdere dupliserte elementer bare en gang.

4. Et binært søk over begge matriser

Kan vi gjøre det bedre enn O (k)? Svaret er at vi kan. Den grunnleggende ideen er å gjøre en binær søkealgoritme over de to matriser.

For at dette skal fungere trenger vi en datastruktur som gir konstant lesetilgang til alle elementene. I Java kan det være en matrise eller en ArrayList.

La oss definere skjelettet for metoden vi skal implementere:

int findKthElement (int k, int [] list1, int [] list2) kaster NoSuchElementException, IllegalArgumentException {// sjekkinngang (se nedenfor) // håndter spesielle tilfeller (se nedenfor) // binært søk (se nedenfor)}

Her passerer vi k og de to matriser som argumenter. Først skal vi validere innspillene; for det andre håndterer vi noen spesielle tilfeller og gjør deretter binært søk. I de neste tre seksjonene vil vi se på disse tre trinnene i omvendt rekkefølge, så først ser vi binært søk, andre, spesielle tilfeller og til slutt parametervalidering.

4.1. The Binary Search

Standard binært søk, der vi leter etter et bestemt element, har to mulige resultater: enten finner vi elementet vi leter etter, og søket er vellykket, eller så finner vi det ikke, og søket mislykkes. Dette er annerledes i vårt tilfelle, der vi vil finne kdet minste elementet. Her har vi alltid et resultat.

La oss se på hvordan vi kan implementere det.

4.1.1. Finne riktig antall elementer fra begge matriser

Vi starter søket med et visst antall elementer fra den første matrisen. La oss ringe det nummeret nElementsList1. Som vi trenger k elementer totalt, antallet nElementsList1 er:

int nElementsList2 = k - nElementsList1; 

La oss si som et eksempel k = 8. Vi starter med fire elementer fra den første matrisen og fire elementer fra den andre matrisen (a).

Hvis det fjerde elementet i den første matrisen er større enn det fjerde elementet i den andre matrisen, vet vi at vi tok for mange elementer fra den første matrisen og kan reduseres nElementsList1 (b). Ellers vet vi at vi tok for få elementer og kan øke nElementsList1 (b ').

Vi fortsetter til vi har nådd stoppekriteriene. Før vi ser på hva det er, la oss se på koden for det vi har beskrevet hittil:

int høyre = k; int venstre = = 0; gjør {nElementsList1 = ((venstre + høyre) / 2) + 1; nElementsList2 = k - nElementsList1; if (nElementsList2> 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } annet {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2));

4.1.2. Stoppekriterier

Vi kan stoppe i to tilfeller. Først kan vi stoppe hvis det maksimale elementet vi tar fra den første matrisen er lik det maksimale elementet vi tar fra det andre (c). I dette tilfellet kan vi bare returnere det elementet.

For det andre kan vi stoppe hvis følgende to betingelser er oppfylt (d):

• Det største elementet å ta fra den første matrisen er mindre enn det minste elementet vi ikke tar fra den andre matrisen (11 < 100).
• Det største elementet å ta fra den andre matrisen er mindre enn det minste elementet vi ikke tar fra den første matrisen (21 < 27).

Det er lett å visualisere (d ') hvorfor denne tilstanden fungerer: alle elementene vi tar fra de to matriser er sikkert mindre enn noe annet element i de to matriser.

Her er koden for stoppekriteriene:

privat statisk boolsk funnetCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// vi tar ikke noe element fra den andre listen hvis (nElementsList2 <1) {return true; } if (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == list1.length) {return list1 [nElementsList1-1] <= list2 [nElementsList2]; } if (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } returliste1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

4.1.3. Returverdien

Til slutt må vi returnere riktig verdi. Her har vi tre mulige tilfeller:

• Vi tar ingen elementer fra den andre matrisen, og dermed er målverdien i den første matrisen (e)
• Målverdien er i den første matrisen (e ')
• Målverdien er i den andre matrisen (e ”)

La oss se dette i kode:

returnere nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]);

Merk at vi ikke trenger å håndtere saken der vi ikke tar noe element fra den første matrisen - vi ekskluderer saken i behandlingen av spesielle saker senere.

4.2. Innledende verdier for venstre og høyre grense

Inntil nå initialiserte vi høyre og venstre kant for den første matrisen med k og 0:

int høyre = k; int venstre = 0;

Avhengig av verdien på k, vi trenger å tilpasse disse grensene.

Først hvis k overstiger lengden på den første matrisen, må vi ta det siste elementet som høyre kant. Årsaken til dette er ganske grei, ettersom vi ikke kan ta flere elementer fra matrisen enn det er.

For det andre, hvis k er større enn antall elementer i den andre matrisen, vet vi helt sikkert at vi må ta minst (k - lengde (liste2)) fra den første matrisen. La oss si som et eksempel k = 7. Siden den andre matrisen bare har fire elementer, vet vi at vi må ta minst 3 elementer fra den første matrisen, slik at vi kan stille inn L til 2:

Her er koden for de tilpassede venstre og høyre kantene:

// riktig venstre grense hvis k er større enn størrelsen på list2 int left = k <list2.length? 0: k - liste2.lengde - 1; // den innvendige høyre grensen kan ikke overstige listen1 int høyre = min (k-1, liste1.lengde - 1);

4.3. Håndtering av spesielle saker

Før vi gjør det faktiske binære søket, kan vi håndtere noen spesielle tilfeller for å gjøre algoritmen litt mindre komplisert og unngå unntak. Her er koden med forklaringer i kommentarene:

// vi ser etter minimumsverdien hvis (k == 1) {retur min (liste1 [0], liste2 [0]); } // vi leter etter maksimumsverdien hvis (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // bytt lister om nødvendig for å sikre at vi tar minst ett element fra liste1 hvis (k <= liste2.lengde && liste2 [k-1] <liste1 [0]) {int [] liste1_ = liste1; liste1 = liste2; liste2 = liste1_; }

4.4. Inngangsvalidering

La oss se på inngangsvalidering først. For å forhindre at algoritmen svikter og kaster, for eksempel en NullPointerException eller ArrayIndexOutOfBoundsException, vi vil forsikre oss om at de tre parametrene oppfyller følgende betingelser:

• Begge matriser må ikke være det null og har minst ett element
• k må være >= 0 og kan ikke være større enn lengden på de to gruppene sammen

Her er vår validering i kode:

void checkInput (int k, int [] list1, int [] list2) kaster NoSuchElementException, IllegalArgumentException {if (list1 == null || list2 == null || k list1.length + list2.length) {kast ny NoSuchElementException () ; }}

4.5. Full kode

Her er den fulle koden til algoritmen vi nettopp har beskrevet:

public static int findKthElement (int k, int [] list1, int [] list2) kaster NoSuchElementException, IllegalArgumentException {checkInput (k, list1, list2); // vi ser etter minimumsverdien hvis (k == 1) {retur min (liste1 [0], liste2 [0]); } // vi leter etter maksimumsverdien hvis (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // bytt lister om nødvendig for å sikre at vi tar minst ett element fra liste1 hvis (k <= liste2.lengde && liste2 [k-1] <liste1 [0]) {int [] liste1_ = liste1; liste1 = liste2; liste2 = liste1_; } // rett venstre grense hvis k er større enn størrelsen på list2 int left = k 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } annet {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2)); returnere nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]); } privat statisk boolsk funnetCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// vi tar ikke noe element fra den andre listen hvis (nElementsList2 <1) {return true; } if (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == list1.length) {return list1 [nElementsList1-1] <= list2 [nElementsList2]; } if (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } returliste1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

5. Testing av algoritmen

I vårt GitHub-arkiv er det mange testtilfeller som dekker mange mulige inngangsarrayer og også mange hjørnesaker.

Her peker vi bare på en av testene, som ikke tester mot statiske inngangsarrayer, men sammenligner resultatet av vår dobbelte binære søkealgoritme med resultatet av den enkle sammenkoblingsalgoritmen. Inngangen består av to randomiserte matriser:

int [] sortedRandomIntArrayOfLength (int length) {int [] intArray = new Random (). ints (length) .toArray (); Arrays.sort (intArray); returnere intArray; }

Følgende metode utfører en enkelt test:

private void random () {Random random = new Random (); int lengde1 = (Math.abs (random.nextInt ()))% 1000 + 1; int lengde2 = (Math.abs (random.nextInt ()))% 1000 + 1; int [] list1 = sortedRandomIntArrayOfLength (lengde1); int [] list2 = sortedRandomIntArrayOfLength (lengde2); int k = (Math.abs (random.nextInt ()) + 1)% (lengde1 + lengde2); int resultat = findKthElement (k, liste1, liste2); int resultat2 = getKthElementSorted (liste1, liste2, k); int result3 = getKthElementMerge (liste1, liste2, k); assertEquals (resultat2, resultat); assertEquals (resultat2, resultat3); }

Og vi kan kalle metoden ovenfor for å kjøre et stort antall tester slik:

@Test ugyldig randomTests () {IntStream.range (1, 100000) .forEach (i -> random ()); }

6. Konklusjon

I denne artikkelen så vi flere måter å finne kdet minste elementet i foreningen av to sorterte matriser. Først så vi en enkel og grei O (n log n) algoritme, deretter en versjon med kompleksitet På), og sist, en algoritme som kjører inn O (log n).

Den siste algoritmen vi så er en fin teoretisk øvelse; for de fleste praktiske formål bør vi imidlertid vurdere å bruke en av de to første algoritmene, som er mye enklere enn det binære søket over to matriser. Selvfølgelig, hvis ytelse er et problem, kan et binært søk være en løsning.

All koden i denne artikkelen er tilgjengelig på GitHub.