A legfontosabb K elemek megtalálása egy Java tömbben
1. Áttekintés
Ebben az oktatóanyagban különböző megoldásokat fogunk megvalósítani a a k legnagyobb elemei tömbben Java-val. Az idő összetettségének leírására a Big-O jelölést használjuk.
2. Brute-Force Solution
A probléma nyers erővel történő megoldása az iteráljon az adott tömbön keresztül k alkalommal. Minden iterációban megtesszükmegtalálja a legnagyobb értéket. Ezután eltávolítjuk ezt az értéket a tömbből, és felvesszük a kimeneti listába:
public List findTopK (List bemenet, int k) {List tömb = új ArrayList (bemenet); List topKList = new ArrayList (); for (int i = 0; i <k; i ++) {int maxIndex = 0; for (int j = 1; j tömb.get (maxIndex)) {maxIndex = j; }} topKList.add (tömb.eltávolítás (maxIndex)); } return topKList; }
Ha feltételezzük n az adott tömb méretének felel meg, a megoldás időbeli összetettsége az O (n * k). Ezenkívül ez a leghatékonyabb megoldás.
3. Java gyűjteményes megközelítés
Erre a problémára azonban hatékonyabb megoldások léteznek. Ebben a szakaszban kettőt elmagyarázunk a Java gyűjtemények használatával.
3.1. TreeSet
TreeSet van egy Vörös-fekete faadatszerkezet mint gerinc. Ennek eredményeként ennek a halmaznak az értéke hozzáadódik O (log n). TreeSet egy válogatott gyűjtemény. Ezért megtehetjük tegye az összes értéket a TreeSetéskivonat az első k tőlük:
public List findTopK (List input, int k) {Set sortedSet = new TreeSet (Comparator.reverseOrder ()); sortedSet.addAll (input); return sortedSet.stream (). limit (k) .collect (Collectors.toList ()); }
A a megoldás időbeli összetettsége O (n * log n). Ennek mindenekelőtt hatékonyabbnak kell lennie, mint a brute-force megközelítés, ha k ≥ log n.
Fontos erre emlékezni TreeSet nem tartalmaz duplikátumot. Ennek eredményeként a megoldás csak egy különálló értékű bemeneti tömb esetén működik.
3.2. PriorityQueue
PriorityQueue egyHalomadatszerkezet Java-ban. Segítségével elérhetünk egy O (n * log k) megoldás. Sőt, ez gyorsabb megoldás lesz, mint az előző. A megállapított probléma miatt k mindig kisebb, mint a tömb mérete. Szóval, ez azt jelenti O (n * log k) ≤ O (n * log n).
Az algoritmus egyszer ismétlődik az adott tömbön keresztül. Minden egyes iterációnál hozzáadunk egy új elemet a kupachoz. Emellett a kupac méretét kisebbnek vagy egyenlőnek tartjuk k. Tehát el kell távolítanunk extra elemeket a kupacból, és újakat kell hozzáadni. Ennek eredményeként a tömbön keresztüli iteráció után a halom tartalmazza a k legnagyobb értékek:
public List findTopK (List input, int k) {PriorityQueue maxHeap = new PriorityQueue (); input.forEach (szám -> {maxHeap.add (szám); if (maxHeap.size ()> k) {maxHeap.poll ();}}); List topKList = new ArrayList (maxHeap); Gyűjtemények.reverse (topKList); return topKList; }
4. Kiválasztási algoritmus
Számos megközelítés létezik az adott probléma megoldására. És bár ez meghaladja az oktatóanyag kereteit, a Selection algoritmus megközelítést alkalmazvalesz a legjobb mert lineáris időbonyolultságot eredményez.
5. Következtetés
Ebben az oktatóanyagban számos megoldást írtunk le a k tömb legnagyobb elemei.
Szokás szerint a példakód elérhető a GitHubon.