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.


$config[zx-auto] not found$config[zx-overlay] not found