Finne topp K-elementer i en Java Array
1. Oversikt
I denne opplæringen vil vi implementere forskjellige løsninger på problemet med finne k største elementene i en matrise med Java. For å beskrive tidskompleksitet bruker vi Big-O-notasjon.
2. Brute-Force-løsning
Brute-force løsningen på dette problemet er å iterere gjennom den gitte matrisen k ganger. I hver iterasjon, vil vifinn den største verdien. Deretter fjerner vi denne verdien fra matrisen og setter den i utgangslisten:
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 antar det n å være størrelsen på den gitte matrisen, tidskompleksiteten til denne løsningen er O (n * k). Videre er dette den mest ineffektive løsningen.
3. Java Collections Approach
Imidlertid eksisterer det mer effektive løsninger på dette problemet. I denne delen forklarer vi to av dem ved hjelp av Java Collections.
3.1. TreeSet
TreeSet har en Rød-svart tredata struktur som en ryggrad. Som et resultat koster det å sette en verdi på dette settet O (log n). TreeSet er en sortert samling. Derfor kan vi legg alle verdiene i TreeSetogtrekke ut den første k av 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 ()); }De tidskompleksiteten til denne løsningen er O (n * log n). Fremfor alt skal dette være mer effektivt enn brute-force-tilnærmingen hvis k ≥ log n.
Det er viktig å huske det TreeSet inneholder ingen duplikater. Som et resultat, fungerer løsningen bare for en inngangssamling med forskjellige verdier.
3.2. PriorityQueue
PriorityQueue er enHaugdata struktur i Java. Med sin hjelp, vi kan oppnå en O (n * log k) løsning. Videre vil dette være en raskere løsning enn den forrige. På grunn av det oppgitte problemet, k er alltid mindre enn størrelsen på matrisen. Så det betyr det O (n * log k) ≤ O (n * log n).
Algoritmen gjentas en gang gjennom den gitte matrisen. Ved hver iterasjon vil vi legge til et nytt element i dyngen. Vi holder også størrelsen på dyngen til å være mindre enn eller lik k. Så vi må fjerne ekstra elementer fra haugen og legge til nye. Som et resultat, etter at den har gått gjennom matrisen, vil haugen inneholde k største verdier:
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); return topKList; }4. Seleksjonsalgoritme
Det er mange tilnærminger for å løse det gitte problemet. Og selv om det er utenfor omfanget av denne opplæringen, ved hjelp av Selection algoritmemetodenvil være best fordi det gir en lineær tidskompleksitet.
5. Konklusjon
I denne opplæringen har vi beskrevet flere løsninger for å finne k største elementene i en matrise.
Som vanlig er eksempelkoden tilgjengelig på GitHub.
