streamalism.org

1. Prehľad

V tomto tutoriále implementujeme rôzne riešenia problému nájdenie k najväčšie prvky v poli s Java. Na popísanie časovej zložitosti použijeme notáciu Big-O.

2. Riešenie hrubou silou

Riešením tohto problému hrubou silou je iterovať cez dané pole k krát. V každej iterácii budemenájsť najväčšiu hodnotu. Potom túto hodnotu z poľa odstránime a vložíme do výstupného zoznamu:

public List findTopK (List list, int k) {List array = new ArrayList (input); Zoznam topKList = nový ArrayList (); pre (int i = 0; i <k; i ++) {int maxIndex = 0; pre (int j = 1; j pole.get (maxIndex)) {maxIndex = j; }} topKList.add (array.remove (maxIndex)); } návrat topKList; }

Ak predpokladáme n byť veľkosťou daného poľa, časová náročnosť tohto riešenia je O (n * k). Ďalej je to najefektívnejšie riešenie.

3. Prístup k zbierkam Java

Účinnejšie riešenia tohto problému však existujú. V tejto časti vysvetlíme dva z nich pomocou zbierok Java.

3.1. TreeSet

TreeSet má Červeno-čierny stromdátová štruktúra ako chrbtová kosť. Výsledkom je, že hodnota tejto sady stojí O (log n). TreeSet je triedený zber. Preto môžeme vložte všetky hodnoty do TreeSetaextrahovať prvý k z nich:

verejný zoznam findTopK (vstup do zoznamu, int k) {Set seřazenéSet = nový TreeSet (Comparator.reverseOrder ()); sortSet.addAll (vstup); návrat seřazenýSet.stream (). limit (k) .collect (Collectors.toList ()); }

The časová zložitosť tohto riešenia je O (n * log n). Toto by malo byť predovšetkým efektívnejšie ako prístup hrubou silou, ak k ≥ log n.

Je dôležité si to uvedomiť TreeSet neobsahuje žiadne duplikáty. Výsledkom je, že riešenie funguje iba pre vstupné pole s odlišnými hodnotami.

3.2. PriorityQueue

PriorityQueue je aHaldadátová štruktúra v Jave. S jeho pomocou môžeme dosiahnuť O (n * log k) Riešenie. Navyše to bude rýchlejšie riešenie ako predchádzajúce. Z dôvodu uvedeného problému k je vždy menšia ako veľkosť poľa. Znamená to teda O (n * log k) ≤ O (n * log n).

Algoritmus iteruje raz cez dané pole. Pri každej iterácii pridáme do haldy nový prvok. Tiež ponecháme veľkosť haldy, aby bola menšia alebo rovnaká k. Budeme teda musieť z haldy odstrániť ďalšie prvky a pridať nové. Výsledkom bude, že po iterácii poľom bude halda obsahovať znak k najväčšie hodnoty:

verejný zoznam findTopK (vstup do zoznamu, int k) {PriorityQueue maxHeap = nový PriorityQueue (); input.forEach (number -> {maxHeap.add (number); if (maxHeap.size ()> k) {maxHeap.poll ();}}); Zoznam topKList = nový ArrayList (maxHeap); Zbierky.reverzný (topKList); vrátiť topKList; }

4. Algoritmus výberu

Existuje veľa prístupov k riešeniu daného problému. A hoci to presahuje rámec tohto tutoriálu, pomocou prístupu výberového algoritmubude najlepší pretože poskytuje lineárnu časovú zložitosť.

5. Záver

V tomto výučbe sme opísali niekoľko riešení na vyhľadanie k najväčšie prvky v poli.

Ako obvykle je ukážkový kód k dispozícii na GitHub.