streamalism.org

1. Introduktion

I denne artikel vil vi se, hvordan du gør det Find kdet mindste element i foreningen af ​​to sorterede arrays.

Først definerer vi det nøjagtige problem. For det andet ser vi to ineffektive, men ligetil løsninger. For det tredje ser vi på en effektiv løsning baseret på en binær søgning på de to arrays. Endelig vil vi se på nogle tests for at bekræfte, at vores algoritme fungerer.

Vi ser også Java-kodestykker til alle dele af algoritmen. For enkelheds skyld fungerer vores implementering kun på heltal. Imidlertid fungerer den beskrevne algoritme med alle datatyper, der er sammenlignelige og endda kunne implementeres ved hjælp af Generics.

2. Hvad er Kdet mindste element i Unionen af ​​to sorterede arrays?

2.1. Det Kdet mindste element

For at finde kdet mindste element, også kaldet kth-order-statistik i en matrix bruger vi typisk en markeringsalgoritme. Disse algoritmer fungerer dog på et enkelt usorteret array, mens vi i denne artikel vil finde kdet mindste element i to sorterede arrays.

Før vi ser flere løsninger på problemet, lad os nøjagtigt definere, hvad vi vil opnå. Lad os med det springe direkte ind i et eksempel.

Vi får to sorterede arrays (-en og b), som ikke nødvendigvis behøver at have lige mange elementer:

I disse to arrays ønsker vi at finde kdet mindste element. Mere specifikt ønsker vi at finde kdet mindste element i det kombinerede og sorterede array:

Det kombinerede og sorterede array til vores eksempel er vist i (c). Det 1. mindste element er 3, og 4. plads mindste element er 20.

2.2. Kopier af værdier

Vi bliver også nødt til at definere, hvordan vi skal håndtere duplikatværdier. Et element kan forekomme mere end én gang i en af ​​matrixerne (element 3 i matrix -en) og forekommer også igen i det andet array (b).

Hvis vi kun tæller dubletter en gang, tæller vi som vist i (c). Hvis vi tæller alle forekomster af et element, tæller vi som vist i (d).

I den resterende del af denne artikel tæller vi duplikater som vist i (d) og tæller dem således som om de var forskellige elementer.

3. To enkle, men mindre effektive tilgange

3.1. Deltag i og sorter derefter de to arrays

Den enkleste måde at finde kdet mindste element er at slutte sig til arrays, sortere dem og returnere kelement i det resulterende array:

int getKthElementSorted (int [] liste1, int [] liste2, int k) {int længde1 = liste1.længde, længde2 = liste2.længde; int [] combinedArray = ny int [længde1 + længde2]; System.arraycopy (liste1, 0, combinedArray, 0, liste1.længde); System.arraycopy (liste2, 0, combinedArray, liste1.længde, liste2.længde); Arrays.sort (combinedArray); retur kombineretArray [k-1]; }

Med n er længden af ​​det første array og m længden af ​​det andet array, får vi den kombinerede længde c = n + m.

Da kompleksiteten for sorteringen er O (c log c)er den samlede kompleksitet af denne tilgang O (n log n).

En ulempe ved denne tilgang er, at vi har brug for at oprette en kopi af arrayet, hvilket resulterer i mere behov for plads.

3.2. Flet de to arrays

Svarende til et enkelt trin i Merge Sort-sorteringsalgoritmen, kan vi flette de to arrays og derefter direkte hente kelement.

Den grundlæggende idé med fletningsalgoritmen er at starte med to markører, der peger på de første elementer i det første og det andet felt (a).

Vi sammenligner derefter de to elementer (3 og 4) ved markørerne, tilføj den mindre (3) til resultatet, og flyt markøren en position fremad (b). Igen sammenligner vi elementerne ved markørerne og tilføjer den mindre (4) til resultatet.

Vi fortsætter på samme måde, indtil alle elementer føjes til det resulterende array. Hvis en af ​​input-arrays ikke har flere elementer, kopierer vi simpelthen alle de resterende elementer i den anden input-array til resultat-arrayet.

Vi kan forbedre ydeevnen, hvis vi ikke kopierer de fulde arrays, men stopper, når den resulterende array har k elementer. Vi behøver ikke engang at oprette et ekstra array til det kombinerede array, men kan kun fungere på de originale arrays.

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 ++; } andet {i2 ++; }} hvis ((i1 + i2) <k) {return i1 0 && i2> 0) {return Math.max (list1 [i1-1], list2 [i2-1]); } andet {return i1 == 0? liste2 [i2-1]: liste1 [i1-1]; }}

Det er ligetil at forstå tidskompleksiteten af ​​denne algoritme er O (k). En fordel ved denne algoritme er, at den let kan tilpasses til kun at overveje duplikerede elementer en gang.

4. En binær søgning over begge arrays

Kan vi gøre det bedre end O (k)? Svaret er, at vi kan. Den grundlæggende idé er at lave en binær søgealgoritme over de to arrays.

For at dette skal fungere, har vi brug for en datastruktur, der giver læseadgang i konstant tid til alle dens elementer. I Java kan det være et array eller et ArrayList.

Lad os definere skeletet til den metode, vi skal implementere:

int findKthElement (int k, int [] list1, int [] list2) kaster NoSuchElementException, IllegalArgumentException {// check input (se nedenfor) // håndter specielle tilfælde (se nedenfor) // binær søgning (se nedenfor)}

Her passerer vi k og de to arrays som argumenter. Først validerer vi input; for det andet håndterer vi nogle specielle tilfælde og udfører derefter binær søgning. I de næste tre sektioner ser vi på disse tre trin i omvendt rækkefølge, så først ser vi den binære søgning, for det andet de specielle tilfælde og endelig parametervalideringen.

4.1. Den binære søgning

Standard binær søgning, hvor vi leder efter et bestemt element, har to mulige resultater: enten finder vi det element, vi leder efter, og søgningen er vellykket, eller vi finder det ikke, og søgningen mislykkes. Dette er anderledes i vores tilfælde, hvor vi ønsker at finde kdet mindste element. Her har vi altid et resultat.

Lad os se på, hvordan vi implementerer det.

4.1.1. Find det korrekte antal elementer fra begge arrays

Vi starter vores søgning med et bestemt antal elementer fra det første array. Lad os ringe til det nummer nElementsList1. Som vi har brug for k elementer i alt, antallet nElementsList1 er:

int nElementsList2 = k - nElementsList1; 

Lad os som et eksempel sige k = 8. Vi starter med fire elementer fra det første array og fire elementer fra det andet array (a).

Hvis det 4. element i det første array er større end det 4. element i det andet array, ved vi, at vi tog for mange elementer fra det første array og kan falde nElementsList1 (b). Ellers ved vi, at vi tog for få elementer og kan øges nElementsList1 (b ').

Vi fortsætter, indtil vi har nået stopkriterierne. Før vi ser på hvad det er, lad os se på koden til det, vi hidtil har beskrevet:

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

4.1.2. Stopkriterier

Vi kan stoppe i to tilfælde. For det første kan vi stoppe, hvis det maksimale element, vi tager fra det første array, er lig med det maksimale element, vi tager fra det andet (c). I dette tilfælde kan vi simpelthen returnere dette element.

For det andet kan vi stoppe, hvis følgende to betingelser er opfyldt (d):

• Det største element, der skal tages fra det første array, er mindre end det mindste element, vi ikke tager fra det andet array (11 < 100).
• Det største element, der skal tages fra det andet array, er mindre end det mindste element, vi ikke tager fra det første array (21 < 27).

Det er let at visualisere (d ') hvorfor denne betingelse fungerer: alle elementer, vi tager fra de to arrays, er helt sikkert mindre end noget andet element i de to arrays.

Her er koden til stopkriterierne:

privat statisk boolsk fundetCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// vi tager ikke noget element fra den anden liste, hvis (nElementsList2 <1) {returner sand; } hvis (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } hvis (nElementsList1 == list1.length) {return list1 [nElementsList1-1] <= list2 [nElementsList2]; } hvis (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } returliste1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

4.1.3. Returværdien

Endelig skal vi returnere den korrekte værdi. Her har vi tre mulige tilfælde:

• Vi tager ingen elementer fra det andet array, så målværdien er i det første array (e)
• Målværdien er i den første matrix (e ')
• Målværdien er i det andet array (e ”)

Lad os se dette i kode:

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

Bemærk, at vi ikke behøver at håndtere sagen, hvor vi ikke tager noget element fra den første matrix - vi udelukker sagen i behandlingen af ​​specielle sager senere.

4.2. Indledende værdier for venstre og højre grænse

Indtil nu initialiserede vi højre og venstre kant til det første array med k og 0:

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

Afhængigt af værdien af k, vi er nødt til at tilpasse disse grænser.

Først hvis k overstiger længden af ​​det første array, skal vi tage det sidste element som den højre kant. Årsagen til dette er ret ligetil, da vi ikke kan tage flere elementer fra arrayet, end der er.

For det andet, hvis k er større end antallet af elementer i det andet array, ved vi med sikkerhed, at vi skal tage mindst (k - længde (liste2)) fra det første array. Lad os som et eksempel sige k = 7. Da den anden matrix kun har fire elementer, ved vi, at vi skal tage mindst 3 elementer fra den første matrix, så vi kan indstille L til 2:

Her er koden til de tilpassede venstre og højre grænser:

// rette venstre grænse, hvis k er større end størrelsen på list2 int left = k <list2.length? 0: k - liste2.længde - 1; // den oprindelige højre grænse kan ikke overstige listen1 int højre = min (k-1, liste1.længde - 1);

4.3. Håndtering af specielle sager

Før vi foretager den egentlige binære søgning, kan vi håndtere et par specielle tilfælde for at gøre algoritmen lidt mindre kompliceret og undgå undtagelser. Her er koden med forklaringer i kommentarerne:

// vi leder efter minimumsværdien, hvis (k == 1) {return min (list1 [0], list2 [0]); } // vi leder efter den maksimale værdi, hvis (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // skift lister, hvis det er nødvendigt for at sikre, at vi tager mindst et element fra liste1 hvis (k <= liste2.længde && liste2 [k-1] <liste1 [0]) {int [] liste1_ = liste1; liste1 = liste2; liste2 = liste1_; }

4.4. Inputvalidering

Lad os se på inputvalideringen først. For at forhindre, at algoritmen fejler og smider, f.eks NullPointerException eller ArrayIndexOutOfBoundsException, Vi vil sikre os, at de tre parametre opfylder følgende betingelser:

• Begge arrays må ikke være nul og har mindst et element
• k må være >= 0 og kan ikke være større end længden af ​​de to arrays sammen

Her er vores 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. Fuld kode

Her er den fulde kode for den algoritme, vi lige har beskrevet:

offentlig statisk int findKthElement (int k, int [] liste1, int [] liste2) kaster NoSuchElementException, IllegalArgumentException {checkInput (k, list1, list2); // vi leder efter minimumsværdien, hvis (k == 1) {return min (list1 [0], list2 [0]); } // vi leder efter den maksimale værdi, hvis (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // skift lister, hvis det er nødvendigt for at sikre, at vi tager mindst et element fra liste1 hvis (k <= liste2.længde && liste2 [k-1] <liste1 [0]) {int [] liste1_ = liste1; liste1 = liste2; liste2 = liste1_; } // korrekt venstre grænse, hvis k er større end størrelsen på list2 int left = k 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } andet {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2)); returnere nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]); } privat statisk boolsk fundetCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// vi tager ikke noget element fra den anden liste, hvis (nElementsList2 <1) {returner sand; } hvis (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } hvis (nElementsList1 == list1.length) {return list1 [nElementsList1-1] <= list2 [nElementsList2]; } hvis (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } returliste1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

5. Test af algoritmen

I vores GitHub-arkiv er der mange testtilfælde, der dækker mange mulige inputarrays og også mange hjørnesager.

Her påpeger vi kun en af ​​testene, som ikke tester mod statiske input-arrays, men sammenligner resultatet af vores dobbelte binære søgealgoritme med resultatet af den enkle sammenkædnings- og sorteringsalgoritme. Indgangen består af to randomiserede arrays:

int [] sortedRandomIntArrayOfLength (int længde) {int [] intArray = ny tilfældig (). ints (længde) .toArray (); Arrays.sort (intArray); returnere intArray; }

Følgende metode udfører en enkelt test:

privat ugyldigt tilfældigt () {Tilfældigt tilfældigt = nyt tilfældigt (); int længde1 = (Math.abs (random.nextInt ()))% 1000 + 1; int længde2 = (Math.abs (random.nextInt ()))% 1000 + 1; int [] list1 = sortedRandomIntArrayOfLength (længde1); int [] list2 = sortedRandomIntArrayOfLength (længde2); int k = (Math.abs (random.nextInt ()) + 1)% (længde1 + længde2); int resultat = findKthElement (k, liste1, liste2); int resultat2 = getKthElementSorted (liste1, liste2, k); int resultat3 = getKthElementMerge (liste1, liste2, k); assertEquals (resultat2, resultat); assertEquals (resultat2, resultat3); }

Og vi kan kalde ovenstående metode til at køre et stort antal tests som den:

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

6. Konklusion

I denne artikel så vi flere måder, hvordan man finder kdet mindste element i foreningen af ​​to sorterede arrays. Først så vi en enkel og ligetil O (n log n) algoritme, derefter en version med kompleksitet På)og sidst en algoritme, der kører ind O (log n).

Den sidste algoritme, vi så, er en god teoretisk øvelse; af de mest praktiske formål bør vi dog overveje at bruge en af ​​de to første algoritmer, som er meget enklere end binær søgning over to arrays. Selvfølgelig, hvis ydeevne er et problem, kan en binær søgning være en løsning.

Al koden i denne artikel er tilgængelig på GitHub.