streamalism.org

1. Introduksjon

I denne artikkelen presenterer vi forskjellige løsninger for å finne kdet største elementet i en sekvens av unike tall. Vi bruker en rekke heltall for eksemplene våre.

Vi vil også snakke om hver algoritmes gjennomsnitt og tidskompleksitet i verste fall.

2. Løsninger

La oss nå utforske noen få mulige løsninger - en som bruker en vanlig sortering og to som bruker Quick Select-algoritmen avledet fra Quick Sort.

2.1. Sortering

Når vi tenker på problemet, kanskje den mest åpenbare løsningen som kommer til hjernen erfor å sortere matrisen.

La oss definere trinnene som kreves:

• Sorter matrisen i stigende rekkefølge
• Som det siste elementet i matrisen ville være det største elementet, kdet største elementet ville være på xth indeks, hvor x = lengde (matrise) - k

Som vi kan se, er løsningen grei, men krever sortering av hele matrisen. Derfor vil tidskompleksiteten være O (n * logn):

public int findKthLargestBySorting (Integer [] arr, int k) {Arrays.sort (arr); int targetIndex = arr. lengde - k; retur arr [targetIndex]; }

En alternativ tilnærming er å sortere matrisen i synkende rekkefølge og bare sette elementet på igjen (k-1)th indeks:

public int findKthLargestBySortingDesc (Integer [] arr, int k) {Arrays.sort (arr, Collections.reverseOrder ()); retur arr [k-1]; }

2.2. QuickSelect

Dette kan betraktes som en optimalisering av forrige tilnærming. I dette velger vi QuickSort for sortering. Når vi analyserer problemstillingen, innser vi det vi trenger faktisk ikke å sortere hele matrisen - vi trenger bare å omorganisere innholdet slik at kelementet i matrisen er kth største eller minste.

I QuickSort velger vi et dreieelement og flytter det til riktig posisjon. Vi deler også matrisen rundt den. I QuickSelect er ideen å stoppe på det punktet hvor selve pivoten er kdet største elementet.

Vi kan optimalisere algoritmen ytterligere hvis vi ikke går igjen for både venstre og høyre side av svinget. Vi trenger bare å komme tilbake for en av dem i henhold til dreieposisjonen.

La oss se på de grunnleggende ideene til QuickSelect-algoritmen:

• Velg et dreieelement og del partisjonen deretter
  • Velg elementet lengst til høyre som pivot
  • Bland rekkefølgen på nytt slik at pivotelementet plasseres på sitt rette sted - alle elementer som er mindre enn pivot vil være ved lavere indekser, og elementer som er større enn pivot vil bli plassert ved høyere indekser enn pivot
• Hvis pivot er plassert ved kelementet i matrisen, avslutt prosessen, da pivot er kdet største elementet
• Hvis dreieposisjonen er større enn k, fortsett deretter prosessen med venstre subarray, ellers, gjenta prosessen med høyre subarray

Vi kan skrive generisk logikk som kan brukes til å finne kdet minste elementet også. Vi definerer en metode findKthElementByQuickSelect () som vil returnere kelement i den sorterte matrisen.

Hvis vi sorterer matrisen i stigende rekkefølge, blir kelementet i en matrise vil være kdet minste elementet. For å finne kdet største elementet, kan vi passere k = lengde (Array) - k.

La oss implementere denne løsningen:

public int findKthElementByQuickSelect (Integer [] arr, int left, int right, int k) {if (k> = 0 && k k) {return findKthElementByQuickSelect (arr, left, pos - 1, k); } returner findKthElementByQuickSelect (arr, pos + 1, høyre, k - pos + venstre - 1); } returner 0; }

La oss nå implementere skillevegg metode, som plukker elementet lengst til høyre som en pivot, setter det på riktig indeks og partisjonerer matrisen på en slik måte at elementer ved lavere indekser skal være mindre enn pivotelementet.

Tilsvarende vil elementer ved høyere indekser være større enn dreieelementet:

offentlig int-partisjon (Heltall [] arr, int venstre, int høyre) {int pivot = arr [høyre]; Heltall [] venstreArr; Heltall [] høyreArr; leftArr = IntStream.range (venstre, høyre) .filter (i -> arr [i] arr [i]). innrammet () .toArray (Heltall [] :: ny); rightArr = IntStream.range (venstre, høyre) .filter (i -> arr [i]> pivot). kart (i -> arr [i]) .bokset () .toArray (Heltall [] :: ny); 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); retur venstre + venstreArraySize; }

Det er en enklere, iterativ tilnærming for å oppnå partisjonering:

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 ++; }} bytte (arr, i, høyre); returnere jeg; } offentlig tomrombytte (Heltall [] arr, int n1, int n2) {int temp = arr [n2]; arr [n2] = arr [n1]; arr [n1] = temp; }

Denne løsningen fungerer På) tid i gjennomsnitt. I verste fall vil imidlertid tidskompleksiteten være O (n ^ 2).

2.3. QuickSelect With Randomized Partition

Denne tilnærmingen er en liten modifikasjon av den forrige tilnærmingen. Hvis matrisen er nesten / fullstendig sortert, og hvis vi velger elementet til høyre som en pivot, vil partisjonen til venstre og høyre underarray være svært ujevn.

Denne metoden antyder plukke det opprinnelige dreieelementet på en tilfeldig måte. Vi trenger ikke å endre partisjonslogikken.

I stedet for å ringe skillevegg, kaller vi randomPartition metoden, som velger et tilfeldig element og bytter det med det høyre elementet før du endelig påkaller skillevegg metode.

La oss implementere randomPartition metode:

offentlig int randomPartition (Heltall arr [], int venstre, int høyre) {int n = høyre - venstre + 1; int pivot = (int) (Math.random ()) * n; bytte (arr, venstre + pivot, høyre); returpartisjon (arr, venstre, høyre); }

Denne løsningen fungerer i de fleste tilfeller bedre enn den forrige saken.

Den forventede tidskompleksiteten til randomisert QuickSelect er På).

Imidlertid gjenstår fortsatt den verste tidskompleksiteten O (n ^ 2).

3. Konklusjon

I denne artikkelen diskuterte vi forskjellige løsninger for å finne kdet største (eller minste) elementet i en rekke unike tall. Den enkleste løsningen er å sortere matrisen og returnere kelementet. Denne løsningen har en tidskompleksitet på O (n * logn).

Vi diskuterte også to varianter av Quick Select. Denne algoritmen er ikke grei, men den har en tidskompleksitet på På) i gjennomsnittlige tilfeller.

Som alltid kan den komplette koden for algoritmen finnes på GitHub.