streamalism.org

1. Úvod

V tomto článku predstavíme rôzne riešenia hľadania knajväčší prvok v poradí jedinečných čísel. Pre svoje príklady použijeme pole celých čísel.

Taktiež si povieme o priemernej a najhoršej časovej zložitosti každého algoritmu.

2. Riešenia

Teraz poďme preskúmať niekoľko možných riešení - jedno pomocou obyčajného triedenia a druhé pomocou algoritmu rýchleho výberu odvodeného z rýchleho triedenia.

2.1. Triedenie

Keď uvažujeme o probléme, možno najviditeľnejšie riešenie, ktoré vás napadne, jezoradiť pole.

Poďme definovať požadované kroky:

• Zoraďte pole vzostupne
• Pretože posledným prvkom poľa by bol najväčší prvok, znak knajväčší prvok by bol na x index, kde x = dĺžka (pole) - k

Ako vidíme, riešenie je jednoduché, ale vyžaduje triedenie celého poľa. Z tohto dôvodu bude časová zložitosť O (n * logn):

public int findKthLargestBySorting (Integer [] arr, int k) {Arrays.sort (arr); int targetIndex = dorazová dĺžka - k; návrat arr [targetIndex]; }

Alternatívnym prístupom je zoradiť pole v zostupnom poradí a prvok jednoducho vrátiť (k-1)th index:

public int findKthLargestBySortingDesc (Integer [] arr, int k) {Arrays.sort (arr, Collections.reverseOrder ()); spätný návrat [k-1]; }

2.2. QuickSelect

To možno považovať za optimalizáciu predchádzajúceho prístupu. V tomto vyberieme na triedenie QuickSort. Analýzou vyhlásenia o probléme si to uvedomujeme v skutočnosti nemusíme triediť celé pole - stačí iba zmeniť jeho obsah tak, aby ktým prvkom poľa je knajväčší alebo najmenší.

V programe QuickSort vyberieme otočný prvok a presunieme ho do správnej polohy. Pole tiež rozdelíme okolo neho. Cieľom aplikácie QuickSelect je zastaviť sa v mieste, kde je samotný otočný čap kth najväčší prvok.

Algoritmus môžeme ďalej optimalizovať, ak sa neopakujeme pre ľavú aj pravú stranu čapu. Potrebujeme opakovať iba pre jednu z nich podľa polohy čapu.

Pozrime sa na základné myšlienky algoritmu QuickSelect:

• Vyberte otočný prvok a podľa toho rozdeľte pole
  • Vyberte prvok úplne vpravo ako otočný
  • Preskupiť pole tak, aby bol otočný prvok umiestnený na správnom mieste - všetky prvky menšie ako otočný by boli pri nižších indexoch a prvky väčšie ako otočný by boli umiestnené pri vyšších indexoch ako otočný
• Ak je otočný čap umiestnený na ktým prvkom v poli, ukončite proces, pretože pivot je kth najväčší prvok
• Ak je poloha otočenia väčšia ako k, potom pokračujte v procese s ľavým čiastkovým poľom, inak proces zopakujte s pravým čiastkovým poľom

Môžeme napísať všeobecnú logiku, pomocou ktorej môžeme nájsť kaj ten najmenší prvok. Definujeme metódu findKthElementByQuickSelect () ktorá vráti kv roztriedenom poli.

Ak zoradíme pole vo vzostupnom poradí, znak ktým prvkom poľa bude kth najmenší prvok. Ak chcete nájsť kten najväčší prvok, môžeme prejsť k = dĺžka (pole) - k.

Implementujme toto riešenie:

public int findKthElementByQuickSelect (Integer [] arr, int vľavo, int vpravo, int k) {if (k> = 0 && k k) {return findKthElementByQuickSelect (arr, left, pos - 1, k); } návrat findKthElementByQuickSelect (arr, pos + 1, vpravo, k - pos + vľavo - 1); } návrat 0; }

Teraz poďme implementovať prepážka metóda, ktorá vyberie prvok úplne vpravo ako pivot, umiestni ho na vhodný index a rozdelí pole tak, aby prvky s nižšími indexmi boli menšie ako prvok pivot.

Podobne budú prvky pri vyšších indexoch väčšie ako otočný prvok:

verejný int oddiel (Integer [] arr, int vľavo, int vpravo) {int pivot = arr [vpravo]; Celé číslo [] leftArr; Celé číslo [] rightArr; leftArr = IntStream.range (vľavo, vpravo) .filter (i -> arr [i] arr [i]). boxed () .toArray (Integer [] :: new); rightArr = IntStream.range (vľavo, vpravo) .filter (i -> arr [i]> pivot) .map (i -> arr [i]) .boxed () .toArray (Integer [] :: new); 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); návrat doľava + leftArraySize; }

Existuje jednoduchší a iteračný prístup k dosiahnutiu rozdelenia na oblasti:

public int partitionIterative (Celé číslo [] arr, int vľavo, int vpravo) {int pivot = arr [vpravo], i = vľavo; for (int j = left; j <= right - 1; j ++) {if (arr [j] <= pivot) {swap (arr, i, j); i ++; }} swap (arr, i, vpravo); návrat i; } public void swap (Integer [] arr, int n1, int n2) {int temp = arr [n2]; arr [n2] = arr [n1]; arr [n1] = teplota; }

Toto riešenie funguje v O (n) priemerne čas. V najhoršom prípade však bude časová zložitosť O (n ^ 2).

2.3. QuickSelect s randomizovaným oddielom

Tento prístup je miernou úpravou predchádzajúceho prístupu. Ak je pole takmer / úplne zoradené a ak ako čap vyberieme prvok úplne vpravo, rozdelenie ľavého a pravého podskupiny bude veľmi nerovnomerné.

Táto metóda naznačuje náhodný výber počiatočného otočného prvku. Logiku rozdeľovania však nemusíme meniť.

Namiesto telefonovania prepážka, voláme randomPartition metóda, ktorá vyberie náhodný prvok a zamení ho s prvkom úplne vpravo pred konečným vyvolaním súboru prepážka metóda.

Poďme implementovať randomPartition metóda:

public int randomPartition (Integer arr [], int left, int right) {int n = right - left + 1; int pivot = (int) (Math.random ()) * n; swap (arr, vľavo + pivot, vpravo); spätná priečka (arr, ľavá, pravá); }

Toto riešenie vo väčšine prípadov funguje lepšie ako predchádzajúci prípad.

Očakávaná časová zložitosť randomizovaného programu QuickSelect je O (n).

Najhoršia časová zložitosť však stále zostáva O (n ^ 2).

3. Záver

V tomto článku sme diskutovali o rôznych riešeniach na vyhľadanie knajväčší (alebo najmenší) prvok v rade jedinečných čísel. Najjednoduchším riešením je zoradiť pole a vrátiť znak kth element. Toto riešenie má časovú zložitosť O (n * logn).

Diskutovali sme tiež o dvoch variáciách rýchleho výberu. Tento algoritmus nie je priamy, ale má časovú zložitosť O (n) v priemerných prípadoch.

Úplný kód algoritmu nájdete ako vždy na GitHub.