streamalism.org

1. Oversigt

I denne vejledning implementerer vi forskellige løsninger på problemet med at finde den k største elementer i en matrix med Java. For at beskrive tidskompleksitet bruger vi Big-O-notation.

2. Brute-Force-løsning

Brute-force-løsningen på dette problem er at gentage gennem det givne array k gange. I hver iteration vil vifind den største værdi. Derefter fjerner vi denne værdi fra arrayet og placeres i outputlisten:

public List findTopK (List input, int k) {List array = new ArrayList (input); Liste topKList = ny ArrayList (); for (int i = 0; i <k; i ++) {int maxIndex = 0; for (int j = 1; j array.get (maxIndex)) {maxIndex = j; }} topKList.add (array.remove (maxIndex)); } returner topKList; }

Hvis vi formoder n at være størrelsen på den givne matrix, tidskompleksiteten af ​​denne løsning er O (n * k). Desuden er dette den mest ineffektive løsning.

3. Java-samlingsmetode

Imidlertid findes der mere effektive løsninger på dette problem. I dette afsnit forklarer vi to af dem ved hjælp af Java Collections.

3.1. TreeSet

TreeSet har en Rød-sort trædatastruktur som rygrad. Som et resultat koster det at sætte en værdi på dette sæt O (log n). TreeSet er en sorteret samling. Derfor kan vi sæt alle værdier i TreeSetogudtræk den første k af dem:

public List findTopK (List input, int k) {Set sortedSet = new TreeSet (Comparator.reverseOrder ()); sortedSet.addAll (input); return sortedSet.stream (). limit (k) .collect (Collectors.toList ()); }

Det tidskompleksiteten af ​​denne løsning er O (n * log n). Frem for alt formodes dette at være mere effektivt end brute-force tilgangen, hvis k ≥ log n.

Det er vigtigt at huske det TreeSet indeholder ingen dubletter. Som et resultat fungerer løsningen kun for et input array med forskellige værdier.

3.2. PriorityQueue

PriorityQueue er enBunkedatastruktur i Java. Med sin hjælp, vi kan opnå en O (n * log k) opløsning. Desuden vil dette være en hurtigere løsning end den foregående. På grund af det angivne problem, k er altid mindre end arrayets størrelse. Så det betyder det O (n * log k) ≤ O (n * log n).

Algoritmen itererer én gang gennem det givne array. Ved hver iteration tilføjer vi et nyt element til bunken. Vi holder også størrelsen på bunken mindre end eller lig med k. Så vi bliver nødt til at fjerne ekstra elementer fra bunken og tilføje nye. Som et resultat vil bunken efter iterering gennem arrayet indeholde k største værdier:

public List findTopK (List input, int k) {PriorityQueue maxHeap = new PriorityQueue (); input.forEach (nummer -> {maxHeap.add (nummer); hvis (maxHeap.size ()> k) {maxHeap.poll ();}}); Liste topKList = ny ArrayList (maxHeap); Collections.reverse (topKList); returner topKList; }

4. Markeringsalgoritme

Der er mange tilgange til at løse det givne problem. Og selvom det ligger uden for omfanget af denne vejledning, ved hjælp af Selection algoritmemetodenvil være den bedste fordi det giver en lineær tidskompleksitet.

5. Konklusion

I denne vejledning har vi beskrevet flere løsninger til at finde k største elementer i en matrix.

Som sædvanlig er eksempelkoden tilgængelig på GitHub.