streamalism.org

1. Uvod

U ovom ćemo članku predstaviti različita rješenja za pronalaženje kth najveći element u nizu jedinstvenih brojeva. Za naše ćemo primjere koristiti niz cijelih brojeva.

Također ćemo razgovarati o prosječnoj i najgoroj vremenskoj složenosti svakog algoritma.

2. Rješenja

Sada istražimo nekoliko mogućih rješenja - jedno pomoću obične sortiranja, a drugo pomoću algoritma za brzi odabir izveden iz Quick Sort.

2.1. Sortiranje

Kad razmislimo o problemu, možda najočitije rješenje koje mi padne na pamet jeza sortiranje niza.

Definirajmo potrebne korake:

• Poredaj niz u rastućem redoslijedu
• Kako bi posljednji element niza bio najveći element, ktaj bi najveći element bio na xth indeks, gdje x = duljina (niz) - k

Kao što vidimo, rješenje je jednostavno, ali zahtijeva razvrstavanje cijelog niza. Stoga će vremenska složenost biti O (n * prijava):

javni int findKthLargestBySorting (Integer [] arr, int k) {Arrays.sort (arr); int targetIndex = arr.length - k; povratak arr [targetIndex]; }

Alternativni pristup je sortiranje niza u opadajućem redoslijedu i jednostavno vraćanje elementa (k-1)th indeks:

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

2.2. QuickSelect

To se može smatrati optimizacijom prethodnog pristupa. U ovom odabiremo QuickSort za sortiranje. Analizirajući tvrdnju problema, shvaćamo da zapravo ne trebamo sortirati cijeli niz - samo moramo preurediti njegov sadržaj tako da kth element niza je kth najveći ili najmanji.

U QuickSort-u biramo pivot element i pomičemo ga u njegov ispravan položaj. Također razdvajamo niz oko njega. U QuickSelectu ideja je zaustaviti se na mjestu gdje je sam stožer kth najveći element.

Algoritam možemo dodatno optimizirati ako se ne ponovi i za lijevu i za desnu stranu osovine. Trebamo se ponoviti samo za jednog od njih prema položaju pivota.

Pogledajmo osnovne ideje algoritma QuickSelect:

• Odaberite element zakretanja i u skladu s tim particionirajte niz
  • Odaberite krajnji desni element kao stožer
  • Izmijenite niz tako da se pivot element postavi na pravo mjesto - svi elementi manji od pivota bili bi na nižim indeksima, a elementi veći od pivota smjestili bi se na veće indekse od pivota
• Ako je pivot postavljen na kth elementa u nizu, izađite iz procesa, jer je osovina kth najveći element
• Ako je položaj zakretanja veći od k, zatim nastavite postupak s lijevim podnizom, u suprotnom ponovite postupak s desnim podnizom

Možemo napisati generičku logiku koja se može koristiti za pronalaženje ki najmanji element. Definirat ćemo metodu findKthElementByQuickSelect () koji će vratiti kth element u sortiranom nizu.

Ako sortiramo niz po rastućem redoslijedu, ktaj element niza bit će kth najmanji element. Da biste pronašli kth najveći element, možemo proći k = duljina (niz) - k.

Primijenimo ovo rješenje:

javni int findKthElementByQuickSelect (Integer [] arr, int lijevo, int desno, int k) {if (k> = 0 && k k) {return findKthElementByQuickSelect (arr, lijevo, poz - 1, k); } return findKthElementByQuickSelect (arr, pos + 1, desno, k - poz + lijevo - 1); } return 0; }

Sada provedimo pregrada metoda koja bira krajnji desni element kao pivot, postavlja ga na odgovarajući indeks i razdvaja niz na takav način da elementi na nižim indeksima trebaju biti manji od pivot elementa.

Slično tome, elementi s višim indeksima bit će veći od pivot elementa:

javna int particija (Integer [] arr, int lijevo, int desno) {int pivot = arr [desno]; Cijeli broj [] leftArr; Cijeli broj [] rightArr; leftArr = IntStream.range (lijevo, desno) .filter (i -> arr [i] arr [i]) .boxed () .toArray (Integer [] :: new); rightArr = IntStream.range (lijevo, desno) .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); povratak lijevo + leftArraySize; }

Postoji jednostavniji, iterativni pristup za postizanje particije:

javni int partitionIterative (Integer [] arr, int lijevo, int desno) {int pivot = arr [desno], i = lijevo; for (int j = lijevo; j <= desno - 1; j ++) {if (arr [j] <= pivot) {swap (arr, i, j); i ++; }} swap (arr, i, desno); return i; } zamjena javne praznine (Integer [] arr, int n1, int n2) {int temp = arr [n2]; arr [n2] = arr [n1]; arr [n1] = temp; }

Ovo rješenje djeluje u sustavu Na) vrijeme u prosjeku. Međutim, u najgorem slučaju, vremenska složenost bit će O (n ^ 2).

2.3. QuickSelect s Randomized Partition

Ovaj je pristup lagana modifikacija prethodnog pristupa. Ako je niz gotovo / u potpunosti sortiran i ako kao osovinu odaberemo krajnji desni element, particija lijevog i desnog niza bit će vrlo neujednačena.

Ova metoda sugerira slučajnim odabirom početnog pivot elementa. Ipak ne trebamo mijenjati logiku particioniranja.

Umjesto da zove pregrada, nazivamo randomPartition metoda koja bira slučajan element i zamjenjuje ga s najdesnijim elementom prije nego što konačno pozove pregrada metoda.

Provedimo randomPartition metoda:

javni int randomPartition (Integer arr [], int lijevo, int desno) {int n = desno - lijevo + 1; int pivot = (int) (Math.random ()) * n; zamjena (arr, lijevo + pivot, desno); vrati particiju (arr, lijevo, desno); }

Ovo rješenje u većini slučajeva djeluje bolje od prethodnog slučaja.

Očekivana vremenska složenost randomiziranog QuickSelect-a je Na).

Međutim, i dalje ostaje najgora vremenska složenost O (n ^ 2).

3. Zaključak

U ovom smo članku razgovarali o različitim rješenjima za pronalaženje kth najveći (ili najmanji) element u nizu jedinstvenih brojeva. Najjednostavnije je rješenje razvrstati niz i vratiti kth element. Ovo rješenje vremenski je složeno O (n * prijava).

Također smo razgovarali o dvije varijacije brzog odabira. Ovaj algoritam nije jednostavan, ali vremenski je složen Na) u prosječnim slučajevima.

Kao i uvijek, cjelovit kôd algoritma možete pronaći na GitHubu.