streamalism.org

1. Inleiding

In dit artikel zullen we verschillende oplossingen presenteren voor het vinden van het khet grootste element in een reeks unieke getallen. We gebruiken een reeks gehele getallen voor onze voorbeelden.

We zullen ook praten over de gemiddelde tijd en de complexiteit van de tijd in het slechtste geval van elk algoritme.

2. Oplossingen

Laten we nu een paar mogelijke oplossingen onderzoeken: een met een gewone sortering en twee met behulp van het Quick Select-algoritme dat is afgeleid van Quick Sort.

2.1. Sorteren

Als we over het probleem nadenken, misschien de meest voor de hand liggende oplossing die in je opkomt isom de array te sorteren.

Laten we de vereiste stappen definiëren:

• Sorteer de array in oplopende volgorde
• Aangezien het laatste element van de array het grootste element zou zijn, is de khet grootste element zou zijn xth index, waar x = lengte (matrix) - k

Zoals we kunnen zien, is de oplossing eenvoudig, maar moet de hele array worden gesorteerd. Vandaar dat de tijdcomplexiteit zal zijn O (n * logn):

openbare int findKthLargestBySorting (geheel getal [] arr, int k) {Arrays.sort (arr); int targetIndex = arr.length - k; retourneer arr [targetIndex]; }

Een alternatieve benadering is om de array in aflopende volgorde te sorteren en het element eenvoudig terug te zetten (k-1)de index:

openbare int findKthLargestBySortingDesc (geheel getal [] arr, int k) {Arrays.sort (arr, Collections.reverseOrder ()); retourneer arr [k-1]; }

2.2. QuickSelect

Dit kan worden beschouwd als een optimalisatie van de vorige benadering. Hierin kiezen we de QuickSort om te sorteren. Als we de probleemstelling analyseren, realiseren we ons dat we hoeven niet echt de hele array te sorteren - we hoeven alleen de inhoud te herschikken zodat de kHet element van de array is het kde grootste of kleinste.

In QuickSort kiezen we een draai-element en verplaatsen het naar de juiste positie. We verdelen ook de array eromheen. In QuickSelect is het de bedoeling om te stoppen op het punt waar het draaipunt zelf het khet grootste element.

We kunnen het algoritme verder optimaliseren als we niet terugkeren voor zowel de linker- als de rechterkant van het draaipunt. We hoeven maar voor één ervan terug te komen op basis van de positie van het draaipunt.

Laten we eens kijken naar de basisideeën van het QuickSelect-algoritme:

• Kies een pivot-element en verdeel de array dienovereenkomstig
  • Kies het meest rechtse element als draaipunt
  • Herschik de array zodanig dat het draaipunt op de juiste plaats wordt geplaatst - alle elementen die kleiner zijn dan het draaipunt zouden op lagere indexen staan ​​en elementen die groter zijn dan het draaipunt zouden op een hogere index worden geplaatst dan het draaipunt
• Als het draaipunt is geplaatst op de ke element in de array, verlaat het proces, aangezien spil de khet grootste element
• Als de draaipositie groter is dan k, ga dan verder met het proces met de linker subarray, of herhaal het proces met de rechter subarray

We kunnen generieke logica schrijven die kan worden gebruikt om de kook het kleinste element. We zullen een methode definiëren findKthElementByQuickSelect () die de kth element in de gesorteerde array.

Als we de array in oplopende volgorde sorteren, wordt de kHet element van een array zal de khet kleinste element. Om het khet grootste element kunnen we passeren k = lengte (Array) - k.

Laten we deze oplossing implementeren:

openbare int findKthElementByQuickSelect (Geheel getal [] arr, int left, int right, int k) {if (k> = 0 && k k) {return findKthElementByQuickSelect (arr, left, pos - 1, k); } return findKthElementByQuickSelect (arr, pos + 1, rechts, k - pos + links - 1); } retourneren 0; }

Laten we nu het partitie method, die het meest rechtse element als een pivot kiest, plaatst het op de juiste index en verdeelt de array zodanig dat elementen met lagere indexen kleiner moeten zijn dan het pivot-element.

Evenzo zullen elementen met hogere indexen groter zijn dan het spilelement:

openbare int partitie (Integer [] arr, int left, int right) {int pivot = arr [right]; Geheel getal [] leftArr; Geheel getal [] rightArr; leftArr = IntStream.range (links, rechts) .filter (i -> arr [i] arr [i]) .boxed () .toArray (geheel getal [] :: nieuw); rightArr = IntStream.range (links, rechts) .filter (i -> arr [i]> pivot) .map (i -> arr [i]) .boxed () .toArray (geheel getal [] :: nieuw); int leftArraySize = leftArr.length; System.arraycopy (leftArr, 0, arr, left, leftArraySize); arr [leftArraySize + left] = pivot; System.arraycopy (rightArr, 0, arr, left + leftArraySize + 1, rightArr.length); terug links + leftArraySize; }

Er is een eenvoudigere, iteratieve benadering om de partitionering te bereiken:

public int partitionIterative (Integer [] arr, int left, int right) {int pivot = arr [right], i = left; for (int j = left; j <= right - 1; j ++) {if (arr [j] <= pivot) {swap (arr, i, j); i ++; }} swap (arr, i, right); terugkeer i; } openbare ongeldige swap (Geheel getal [] arr, int n1, int n2) {int temp = arr [n2]; arr [n2] = arr [n1]; arr [n1] = temp; }

Deze oplossing werkt in Aan) tijd gemiddeld. In het ergste geval zal de tijd echter complexiteit zijn O (n ^ 2).

2.3. QuickSelect met willekeurige partitie

Deze benadering is een kleine wijziging van de vorige benadering. Als de array bijna / volledig is gesorteerd en als we het meest rechtse element als draaipunt kiezen, zal de verdeling van de linker en rechter subarrays zeer ongelijk zijn.

Deze methode suggereert het aanvankelijke scharnierelement op een willekeurige manier kiezen. We hoeven de partitioneringslogica echter niet te wijzigen.

In plaats van te bellen partitie, noemen we de randomPartition methode, die een willekeurig element kiest en het verwisselt met het meest rechtse element voordat de partitie methode.

Laten we het randomPartition methode:

public int randomPartition (Integer arr [], int left, int right) {int n = right - left + 1; int pivot = (int) (Math.random ()) * n; swap (arr, links + pivot, rechts); retourpartitie (arr, links, rechts); }

Deze oplossing werkt in de meeste gevallen beter dan het vorige geval.

De verwachte tijdcomplexiteit van gerandomiseerde QuickSelect is Aan).

De ergste tijdcomplexiteit blijft echter bestaan O (n ^ 2).

3. Conclusie

In dit artikel hebben we verschillende oplossingen besproken om de khet grootste (of kleinste) element in een reeks unieke getallen. De eenvoudigste oplossing is om de array te sorteren en de khet element. Deze oplossing heeft een tijdcomplexiteit van O (n * logn).

We hebben ook twee varianten van Quick Select besproken. Dit algoritme is niet eenvoudig, maar het heeft een tijdcomplexiteit van Aan) in gemiddelde gevallen.

Zoals altijd is de volledige code voor het algoritme te vinden op GitHub.