streamalism.org

1. Inleiding

In dit artikel zullen we zien hoe vind de khet kleinste element in de vereniging van twee gesorteerde arrays.

Eerst zullen we het exacte probleem definiëren. Ten tweede zullen we twee inefficiënte maar ongecompliceerde oplossingen zien. Ten derde kijken we naar een efficiënte oplossing op basis van een binaire zoekopdracht op de twee arrays. Ten slotte bekijken we enkele tests om te verifiëren dat ons algoritme werkt.

We zien ook Java-codefragmenten voor alle delen van het algoritme. Voor de eenvoud werkt onze implementatie alleen op gehele getallen. Het beschreven algoritme werkt echter met alle datatypes die vergelijkbaar zijn en zelfs met Generics kunnen worden geïmplementeerd.

2. Wat is het Khet kleinste element in de unie van twee gesorteerde arrays?

2.1. De Khet kleinste element

Om het khet kleinste element, ook wel het kth-order-statistiek, in een array gebruiken we meestal een selectie-algoritme. Deze algoritmen werken echter op een enkele, ongesorteerde array, terwijl we in dit artikel de khet kleinste element in twee gesorteerde arrays.

Voordat we verschillende oplossingen voor het probleem zien, moeten we precies definiëren wat we willen bereiken. Laten we daarvoor meteen naar een voorbeeld springen.

We krijgen twee gesorteerde arrays (een en b), die niet noodzakelijk een gelijk aantal elementen hoeven te hebben:

In deze twee arrays willen we de khet kleinste element. Meer specifiek willen we de khet kleinste element in de gecombineerde en gesorteerde array:

De gecombineerde en gesorteerde array voor ons voorbeeld wordt getoond in (c). De 1e kleinste element is 3, en de 4e kleinste element is 20.

2.2. Dubbele waarden

We zullen ook moeten definiëren hoe dubbele waarden moeten worden afgehandeld. Een element kan meer dan eens voorkomen in een van de arrays (element 3 in reeks een) en komen ook weer voor in de tweede array (b).

Als we duplicaten maar één keer tellen, tellen we zoals weergegeven in (c). Als we alle exemplaren van een element tellen, tellen we zoals weergegeven in (d).

In het resterende deel van dit artikel zullen we duplicaten tellen zoals weergegeven in (d), dus ze tellen alsof het afzonderlijke elementen zijn.

3. Twee eenvoudige maar minder efficiënte benaderingen

3.1. Verbind en sorteer vervolgens de twee arrays

De eenvoudigste manier om het kHet kleinste element is om de arrays samen te voegen, ze te sorteren en de kth element van de resulterende array:

int getKthElementSorted (int [] lijst1, int [] lijst2, int k) {int lengte1 = lijst1.lengte, lengte2 = lijst2.lengte; int [] combinedArray = nieuwe int [lengte1 + lengte2]; System.arraycopy (lijst1, 0, combinedArray, 0, lijst1.lengte); System.arraycopy (lijst2, 0, combinedArray, lijst1.lengte, lijst2.lengte); Arrays.sort (combinedArray); return combinedArray [k-1]; }

Met n zijnde de lengte van de eerste array en m de lengte van de tweede array, krijgen we de gecombineerde lengte c = n + m.

Omdat de complexiteit voor het soort is O (c log c)is de algehele complexiteit van deze benadering O (n log n).

Een nadeel van deze aanpak is dat we een kopie van de array moeten maken, waardoor er meer ruimte nodig is.

3.2. Voeg de twee arrays samen

Vergelijkbaar met een enkele stap van het sorteeralgoritme samenvoegen, kunnen we de twee arrays samenvoegen en vervolgens direct de khet element.

Het basisidee van het samenvoegalgoritme is om te beginnen met twee pointers, die verwijzen naar de eerste elementen van de eerste en tweede arrays (a).

Vervolgens vergelijken we de twee elementen (3 en 4) bij de pointers, voeg de kleinere toe (3) naar het resultaat en verplaats die aanwijzer een positie naar voren (b). Nogmaals, we vergelijken de elementen bij de pointers en voegen de kleinere toe (4) aan het resultaat.

We gaan op dezelfde manier door totdat alle elementen aan de resulterende array zijn toegevoegd. Als een van de invoerarrays niet meer elementen heeft, kopiëren we eenvoudig alle resterende elementen van de andere invoerarray naar de resultaatarray.

We kunnen de prestaties verbeteren als we niet de volledige arrays kopiëren, maar stoppen wanneer de resulterende array dat wel heeft k elementen. We hoeven niet eens een extra array voor de gecombineerde array te maken, maar kunnen alleen op de originele arrays werken.

Hier is een implementatie in Java:

openbare statische int getKthElementMerge (int [] lijst1, int [] lijst2, int k) {int i1 = 0, i2 = 0; while (i1 <list1.length && i2 <list2.length && (i1 + i2) <k) {if (list1 [i1] <list2 [i2]) {i1 ++; } anders {i2 ++; }} if ((i1 + i2) <k) {return i1 0 && i2> 0) {return Math.max (lijst1 [i1-1], lijst2 [i2-1]); } else {return i1 == 0? lijst2 [i2-1]: lijst1 [i1-1]; }}

Het is eenvoudig om te begrijpen dat de tijdcomplexiteit van dit algoritme O is (k). Een voordeel van dit algoritme is dat het gemakkelijk kan worden aangepast om dubbele elementen slechts één keer te beschouwen.

4. Een binaire zoekopdracht in beide arrays

Kunnen we het beter doen dan O (k)? Het antwoord is dat we het kunnen. Het basisidee is om een ​​binair zoekalgoritme uit te voeren over de twee arrays.

Om dit te laten werken, hebben we een datastructuur nodig die constante leestoegang biedt tot al zijn elementen. In Java kan dat een array of een ArrayList.

Laten we het skelet definiëren voor de methode die we gaan implementeren:

int findKthElement (int k, int [] list1, int [] list2) gooit NoSuchElementException, IllegalArgumentException {// controleer invoer (zie hieronder) // behandel speciale gevallen (zie hieronder) // binair zoeken (zie hieronder)}

Hier passeren we k en de twee arrays als argumenten. Eerst valideren we de invoer; ten tweede behandelen we een aantal speciale gevallen en doen dan de binaire zoekactie. In de volgende drie secties bekijken we deze drie stappen in omgekeerde volgorde, dus eerst zien we de binaire zoekactie, ten tweede de speciale gevallen en ten slotte de parametervalidatie.

4.1. De binaire zoekopdracht

De standaard binaire zoekopdracht, waarbij we naar een specifiek element zoeken, heeft twee mogelijke uitkomsten: ofwel vinden we het element dat we zoeken en de zoekopdracht is succesvol, ofwel vinden we het niet en is de zoekopdracht mislukt. Dit is anders in ons geval, waar we de khet kleinste element. Hier hebben we altijd een resultaat.

Laten we eens kijken hoe we dat kunnen implementeren.

4.1.1. Het juiste aantal elementen uit beide arrays zoeken

We beginnen onze zoektocht met een bepaald aantal elementen uit de eerste array. Laten we dat nummer bellen nElementsList1. Zoals we nodig hebben k elementen in totaal, het aantal nElementsList1 is:

int nElementsList2 = k - nElementsList1; 

Laten we als voorbeeld zeggen k = 8. We beginnen met vier elementen uit de eerste array en vier elementen uit de tweede array (a).

Als het 4e element in de eerste array groter is dan het 4e element in de tweede array, weten we dat we te veel elementen uit de eerste array hebben gehaald en kunnen we afnemen nElementsList1 (b). Anders weten we dat we te weinig elementen hebben genomen en kunnen verhogen nElementsList1 (b ').

We gaan door totdat we de stopcriteria hebben bereikt. Voordat we kijken naar wat dat is, kijken we eerst naar de code voor wat we tot nu toe hebben beschreven:

int rechts = k; int left = = 0; doe {nElementsList1 = ((links + rechts) / 2) + 1; nElementsList2 = k - nElementsList1; if (nElementsList2> 0) {if (lijst1 [nElementsList1 - 1]> lijst2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } else {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2));

4.1.2. Criteria stoppen

We kunnen in twee gevallen stoppen. Ten eerste kunnen we stoppen als het maximale element dat we uit de eerste array halen, gelijk is aan het maximale element dat we uit de tweede (c) halen. In dit geval kunnen we dat element eenvoudig retourneren.

Ten tweede kunnen we stoppen als aan de volgende twee voorwaarden is voldaan (d):

• Het grootste element dat we uit de eerste array halen, is kleiner dan het kleinste element dat we niet uit de tweede array halen (11 < 100).
• Het grootste element dat we uit de tweede array halen, is kleiner dan het kleinste element dat we niet uit de eerste array halen (21 < 27).

Het is gemakkelijk te visualiseren (d ') waarom die voorwaarde werkt: alle elementen die we uit de twee arrays halen, zijn zeker kleiner dan elk ander element in de twee arrays.

Hier is de code voor de stopcriteria:

private static boolean foundCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// we nemen geen enkel element uit de tweede lijst if (nElementsList2 <1) {return true; } if (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == lijst1.lengte) {retour lijst1 [nElementsList1-1] <= lijst2 [nElementsList2]; } if (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } retour lijst1 [nElementsList1-1] <= lijst2 [nElementsList2] && lijst2 [nElementsList2-1] <= lijst1 [nElementsList1]; }

4.1.3. De retourwaarde

Ten slotte moeten we de juiste waarde retourneren. Hier hebben we drie mogelijke gevallen:

• We nemen geen elementen uit de tweede array, dus de doelwaarde bevindt zich in de eerste array (e)
• De doelwaarde bevindt zich in de eerste array (e ')
• De doelwaarde bevindt zich in de tweede array (e ")

Laten we dit in code bekijken:

retourneer nElementsList2 == 0? lijst1 [nElementsList1-1]: max (lijst1 [nElementsList1-1], lijst2 [nElementsList2-1]);

Merk op dat we het geval niet hoeven af ​​te handelen waarin we geen enkel element uit de eerste array nemen - we zullen dat geval later uitsluiten bij de behandeling van speciale gevallen.

4.2. Beginwaarden voor de linker- en rechtergrenzen

Tot nu toe hebben we de rechter- en linkerrand voor de eerste array geïnitialiseerd met k en 0:

int rechts = k; int left = 0;

Afhankelijk van de waarde van kmoeten we deze grenzen aanpassen.

Ten eerste, als k de lengte van de eerste array overschrijdt, moeten we het laatste element als rechterrand nemen. De reden hiervoor is vrij eenvoudig, aangezien we niet meer elementen uit de array kunnen nemen dan er zijn.

Ten tweede, als k groter is dan het aantal elementen in de tweede array, weten we zeker dat we tenminste (k - lengte (lijst2)) van de eerste array. Laten we als voorbeeld zeggen k = 7. Omdat de tweede array maar vier elementen heeft, weten we dat we er minimaal moeten nemen 3 elementen uit de eerste array, zodat we kunnen instellen L. naar 2:

Hier is de code voor de aangepaste linker- en rechtergrenzen:

// corrigeer linkergrens als k groter is dan de grootte van list2 int left = k <list2.length? 0: k - lijst2.lengte - 1; // de eerste rechtergrens mag niet groter zijn dan list1 int right = min (k-1, list1.length - 1);

4.3. Behandeling van speciale gevallen

Voordat we de daadwerkelijke binaire zoekopdracht uitvoeren, kunnen we een paar speciale gevallen behandelen om het algoritme iets minder gecompliceerd te maken en uitzonderingen te vermijden. Hier is de code met uitleg in de opmerkingen:

// we zoeken de minimumwaarde if (k == 1) {return min (list1 [0], list2 [0]); } // we zoeken de maximale waarde if (lijst1.lengte + lijst2.lengte == k) {return max (lijst1 [lijst1.lengte-1], lijst2 [lijst2.lengte-1]); } // wissel lijsten indien nodig om er zeker van te zijn dat we ten minste één element uit lijst1 nemen if (k <= lijst2.lengte && lijst2 [k-1] <lijst1 [0]) {int [] lijst1_ = lijst1; list1 = lijst2; list2 = lijst1_; }

4.4. Invoervalidatie

Laten we eerst naar de invoervalidatie kijken. Om te voorkomen dat het algoritme faalt en bijvoorbeeld een NullPointerException of ArrayIndexOutOfBoundsException, we willen er zeker van zijn dat de drie parameters aan de volgende voorwaarden voldoen:

• Beide arrays mogen dat niet zijn nul en hebben tenminste één element
• k moet zijn >= 0 en kunnen niet groter zijn dan de lengte van de twee reeksen samen

Hier is onze validatie in code:

void checkInput (int k, int [] list1, int [] list2) gooit NoSuchElementException, IllegalArgumentException {if (list1 == null || list2 == null || k list1.length + list2.length) {throw new NoSuchElementException () ; }}

4.5. Volledige code

Hier is de volledige code van het algoritme dat we zojuist hebben beschreven:

openbare statische int findKthElement (int k, int [] list1, int [] list2) gooit NoSuchElementException, IllegalArgumentException {checkInput (k, list1, list2); // we zoeken de minimumwaarde if (k == 1) {return min (list1 [0], list2 [0]); } // we zoeken de maximale waarde if (lijst1.lengte + lijst2.lengte == k) {return max (lijst1 [lijst1.lengte-1], lijst2 [lijst2.lengte-1]); } // wissel lijsten indien nodig om er zeker van te zijn dat we ten minste één element uit lijst1 nemen if (k <= lijst2.lengte && lijst2 [k-1] <lijst1 [0]) {int [] lijst1_ = lijst1; list1 = lijst2; list2 = lijst1_; } // corrigeer linkergrens als k groter is dan de grootte van lijst2 int left = k 0) {if (lijst1 [nElementsList1 - 1]> lijst2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } else {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2)); retourneer nElementsList2 == 0? lijst1 [nElementsList1-1]: max (lijst1 [nElementsList1-1], lijst2 [nElementsList2-1]); } private static boolean foundCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// we nemen geen enkel element uit de tweede lijst if (nElementsList2 <1) {return true; } if (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == lijst1.lengte) {retour lijst1 [nElementsList1-1] <= lijst2 [nElementsList2]; } if (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } retour lijst1 [nElementsList1-1] <= lijst2 [nElementsList2] && lijst2 [nElementsList2-1] <= lijst1 [nElementsList1]; }

5. Testen van het algoritme

In onze GitHub-repository zijn er veel testcases die veel mogelijke invoerarrays omvatten en ook veel hoekcases.

Hier wijzen we slechts op één van de tests, die niet test tegen statische invoerarrays, maar het resultaat van ons dubbel-binaire zoekalgoritme vergelijkt met het resultaat van het eenvoudige join-and-sort-algoritme. De invoer bestaat uit twee willekeurige arrays:

int [] gesorteerdRandomIntArrayOfLength (int lengte) {int [] intArray = nieuwe Random (). ints (lengte) .toArray (); Arrays.sort (intArray); retourneer intArray; }

De volgende methode voert één enkele test uit:

private void random () {Random random = new Random (); int length1 = (Math.abs (random.nextInt ()))% 1000 + 1; int length2 = (Math.abs (random.nextInt ()))% 1000 + 1; int [] lijst1 = gesorteerdRandomIntArrayOfLength (lengte1); int [] lijst2 = gesorteerdRandomIntArrayOfLength (lengte2); int k = (Math.abs (random.nextInt ()) + 1)% (length1 + length2); int resultaat = findKthElement (k, lijst1, lijst2); int result2 = getKthElementSorted (lijst1, lijst2, k); int result3 = getKthElementMerge (lijst1, lijst2, k); assertEquals (resultaat2, resultaat); assertEquals (resultaat2, resultaat3); }

En we kunnen de bovenstaande methode aanroepen om een ​​groot aantal dergelijke tests uit te voeren:

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

6. Conclusie

In dit artikel hebben we verschillende manieren gezien om het khet kleinste element in de vereniging van twee gesorteerde arrays. Ten eerste zagen we een eenvoudig en duidelijk O (n log n) algoritme, dan een versie met complexiteit Aan), en als laatste, een algoritme dat wordt uitgevoerd in O (logboek n).

Het laatste algoritme dat we zagen is een mooie theoretische oefening; voor de meeste praktische doeleinden zouden we echter moeten overwegen om een ​​van de eerste twee algoritmen te gebruiken, die veel eenvoudiger zijn dan de binaire zoekactie over twee arrays. Als prestatie een probleem is, kan een binaire zoekopdracht natuurlijk een oplossing zijn.

Alle code in dit artikel is beschikbaar op GitHub.