streamalism.org

1. Introduktion

I denne artikel præsenterer vi forskellige løsninger til at finde kdet største element i en række af unikke tal. Vi bruger en række heltal til vores eksempler.

Vi vil også tale om hver algoritmes gennemsnitlige og værste tilfælde tidskompleksitet.

2. Løsninger

Lad os nu undersøge et par mulige løsninger - en ved hjælp af en almindelig sortering og to ved hjælp af Quick Select-algoritmen afledt af Hurtig sortering.

2.1. Sortering

Når vi tænker på problemet, måske den mest åbenlyse løsning, der kommer til at tænke på, erfor at sortere arrayet.

Lad os definere de nødvendige trin:

• Sorter arrayet i stigende rækkefølge
• Som det sidste element i arrayet ville være det største element, kdet største element ville være ved xth indeks, hvor x = længde (matrix) - k

Som vi kan se, er løsningen ligetil, men kræver sortering af hele arrayet. Derfor vil tidskompleksiteten være O (n * logn):

public int findKthLargestBySorting (Integer [] arr, int k) {Arrays.sort (arr); int targetIndex = arr. længde - k; returnere arr [targetIndex]; }

En alternativ tilgang er at sortere arrayet i faldende rækkefølge og blot returnere elementet (k-1)th indeks:

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

2.2. QuickSelect

Dette kan betragtes som en optimering af den tidligere tilgang. I dette vælger vi QuickSort til sortering. Når vi analyserer problemstillingen, indser vi det vi behøver faktisk ikke sortere hele arrayet - vi behøver kun at omarrangere dets indhold, så kdet element i arrayet er kth største eller mindste.

I QuickSort vælger vi et drejelement og flytter det til sin korrekte position. Vi deler også arrayet omkring det. I QuickSelect er ideen at stoppe ved det punkt, hvor selve omdrejningspunktet er det kdet største element.

Vi kan optimere algoritmen yderligere, hvis vi ikke gentager både venstre og højre side af drejetappen. Vi behøver kun at gentage en af ​​dem alt efter drejepositionen.

Lad os se på de grundlæggende ideer i QuickSelect-algoritmen:

• Vælg et drejelement, og del arrayet i overensstemmelse hermed
  • Vælg elementet til højre som drejning
  • Ombland arrayet, så drejelementet placeres på det rigtige sted - alle elementer mindre end drejningen ville være ved lavere indekser, og elementer større end drejningen ville blive placeret ved højere indekser end drejetappen
• Hvis drejetap er placeret ved kelement i arrayet, afslut processen, da drejning er kdet største element
• Hvis drejeposition er større end k, Fortsæt derefter processen med venstre subarray, ellers gentag processen med højre subarray

Vi kan skrive generisk logik, som kan bruges til at finde kdet mindste element også. Vi definerer en metode findKthElementByQuickSelect () som vil returnere kelement i det sorterede array.

Hvis vi sorterer arrayet i stigende rækkefølge, vises kdet element i en matrix vil være kdet mindste element. For at finde kdet største element, vi kan passere k = længde (Array) - k.

Lad os implementere denne løsning:

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

Lad os nu implementere skillevæg metode, der vælger elementet til højre som en drejetap, placerer det på det relevante indeks og partitionerer arrayet på en sådan måde, at elementer ved lavere indekser skal være mindre end pivotelementet.

Tilsvarende vil elementer ved højere indekser være større end drejelementet:

offentlig int partition (Heltal [] arr, int venstre, int højre) {int pivot = arr [højre]; Heltal [] venstreArr; Heltal [] rightArr; leftArr = IntStream.range (venstre, højre). filter (i -> arr [i] arr [i]). boxed () .toArray (Integer [] :: new); rightArr = IntStream.range (venstre, højre). filter (i -> arr [i]> pivot). kort (i -> arr [i]). boxed () .toArray (Integer [] :: new); int leftArraySize = leftArr.længde; System.arraycopy (leftArr, 0, arr, left, leftArraySize); arr [leftArraySize + venstre] = pivot; System.arraycopy (rightArr, 0, arr, left + leftArraySize + 1, rightArr.length); returnere venstre + venstreArraySize; }

Der er en enklere, iterativ tilgang til at opnå partitioneringen:

public int partitionIterative (Heltal [] arr, int venstre, int højre) {int pivot = arr [højre], i = venstre; for (int j = venstre; j <= højre - 1; j ++) {hvis (arr [j] <= pivot) {swap (arr, i, j); i ++; }} skift (arr, i, højre); returnere i; } offentlig tomrumsbytte (Heltal [] arr, int n1, int n2) {int temp = arr [n2]; arr [n2] = arr [n1]; arr [n1] = temp; }

Denne løsning fungerer i På) tid i gennemsnit. I værste fald vil tidskompleksiteten imidlertid være O (n ^ 2).

2.3. QuickSelect With Randomized Partition

Denne tilgang er en lille ændring af den tidligere tilgang. Hvis matrixen er næsten / fuldt sorteret, og hvis vi vælger det yderste element som en drejetap, vil partitionen af ​​venstre og højre underarray være meget ujævn.

Denne metode antyder vælge det indledende drejelement på en tilfældig måde. Vi behøver dog ikke ændre partitioneringslogikken.

I stedet for at ringe skillevæg, vi kalder randomPartition metode, der vælger et tilfældigt element og bytter det med elementet til højre, inden det endelig påberåbes skillevæg metode.

Lad os implementere randomPartition metode:

offentlig int randomPartition (Heltal arr [], int venstre, int højre) {int n = højre - venstre + 1; int pivot = (int) (Math. tilfældigt ()) * n; swap (arr, venstre + pivot, højre); returpartition (arr, venstre, højre); }

Denne løsning fungerer i de fleste tilfælde bedre end den tidligere sag.

Den forventede tidskompleksitet for randomiseret QuickSelect er På).

Imidlertid er den værste tidskompleksitet stadig O (n ^ 2).

3. Konklusion

I denne artikel diskuterede vi forskellige løsninger for at finde kdet største (eller mindste) element i en række unikke tal. Den enkleste løsning er at sortere arrayet og returnere kelement. Denne løsning har en tidskompleksitet på O (n * logn).

Vi diskuterede også to variationer af Quick Select. Denne algoritme er ikke ligetil, men den har en tidskompleksitet på På) i gennemsnitlige tilfælde.

Som altid kan den komplette kode til algoritmen findes på GitHub.