streamalism.org

1. Pregled

U ovom uputstvu implementirat ćemo različita rješenja problema pronalaženje k najveći elementi u nizu s Javom. Za opisivanje vremenske složenosti koristit ćemo Big-O notaciju.

2. Brute-Force rješenje

Grubo rješenje ovog problema je iterirati kroz zadani niz k puta. U svakoj iteraciji, mi ćemonaći najveću vrijednost. Tada ćemo ukloniti ovu vrijednost iz niza i staviti na izlazni popis:

javni popis findTopK (Unos popisa, int k) {Niz popisa = novi ArrayList (ulaz); Popis topKList = novi ArrayList (); za (int i = 0; i <k; i ++) {int maxIndex = 0; for (int j = 1; j array.get (maxIndex)) {maxIndex = j; }} topKList.add (array.remove (maxIndex)); } return topKList; }

Ako pretpostavimo n da bude veličina datog niza, vremenska složenost ovog rješenja je O (n * k). Nadalje, ovo je najneučinkovitije rješenje.

3. Pristup Java zbirkama

Međutim, postoje učinkovitija rješenja za ovaj problem. U ovom ćemo odjeljku objasniti dva od njih pomoću Java zbirki.

3.1. TreeSet

TreeSet ima Crveno-crno drvostruktura podataka kao okosnica. Kao rezultat, stavljanje vrijednosti ovom skupu košta O (zapisnik n). TreeSet je sortirana zbirka. Stoga možemo stavite sve vrijednosti u TreeSetiizvadi prvu k od njih:

javni popis findTopK (Unos popisa, int k) {Postavi sortedSet = novi TreeSet (Comparator.reverseOrder ()); sortedSet.addAll (ulaz); vrati sortedSet.stream (). limit (k) .collect (Collectors.toList ()); }

The vremenska složenost ovog rješenja je O (n * log n). Iznad svega, ovo bi trebalo biti učinkovitije od grube sile ako k ≥ log n.

Važno je to upamtiti TreeSet ne sadrži duplikate. Kao rezultat, rješenje radi samo za ulazni niz s različitim vrijednostima.

3.2. PriorityQueue

PriorityQueue jeHrpastruktura podataka na Javi. Uz njegovu pomoć, možemo postići O (n * log k) riješenje. Štoviše, ovo će biti brže rješenje od prethodnog. Zbog navedenog problema, k je uvijek manja od veličine polja. Dakle, to znači O (n * log k) ≤ O (n * log n).

Algoritam ponavlja se jednom kroz zadani niz. U svakoj iteraciji na hrpu ćemo dodati novi element. Također, držat ćemo veličinu hrpe manjom ili jednakom k. Dakle, morat ćemo ukloniti dodatne elemente iz hrpe i dodati nove. Kao rezultat, nakon iteriranja kroz niz, hrpa će sadržavati k najveće vrijednosti:

javni popis findTopK (Unos popisa, int k) {PriorityQueue maxHeap = novi PriorityQueue (); input.forEach (number -> {maxHeap.add (number); if (maxHeap.size ()> k) {maxHeap.poll ();}}); Popis topKList = novi ArrayList (maxHeap); Collections.reverse (topKList); povratak topKList; }

4. Algoritam odabira

Postoji mnogo pristupa rješavanju zadanog problema. I, iako je to izvan opsega ovog vodiča, koristeći pristup algoritma za odabirbit će najbolji jer daje linearnu vremensku složenost.

5. Zaključak

U ovom uputstvu opisali smo nekoliko rješenja za pronalaženje k najveći elementi u nizu.

Kao i obično, primjer koda dostupan je na GitHubu.