Top K-elementen vinden in een Java-array
1. Overzicht
In deze tutorial zullen we verschillende oplossingen implementeren voor het probleem van het vinden van de k grootste elementen in een array met Java. Om tijdcomplexiteit te beschrijven, gebruiken we de Big-O-notatie.
2. Brute-Force-oplossing
De brute-force oplossing voor dit probleem is om doorloop de gegeven array k keer. In elke iteratie zullen wevind de grootste waarde. Vervolgens zullen we deze waarde uit de array verwijderen en in de uitvoerlijst plaatsen:
openbare lijst findTopK (Lijstinvoer, int k) {Lijstmatrix = nieuwe ArrayList (invoer); Lijst topKList = nieuwe ArrayList (); voor (int i = 0; i <k; i ++) {int maxIndex = 0; voor (int j = 1; j array.get (maxIndex)) {maxIndex = j; }} topKList.add (array.remove (maxIndex)); } return topKList; }Als we veronderstellen n om de grootte van de gegeven array te zijn, de tijdcomplexiteit van deze oplossing is O (n * k). Bovendien is dit de meest inefficiënte oplossing.
3. Aanpak van Java-verzamelingen
Er bestaan echter efficiëntere oplossingen voor dit probleem. In dit gedeelte zullen we er twee uitleggen met behulp van Java-verzamelingen.
3.1. TreeSet
TreeSet heeft een Rood-zwarte boomdata structuur als ruggengraat. Als gevolg hiervan kost het waarderen van deze set O (logboek n). TreeSet is een gesorteerde verzameling. Daarom kunnen we zet alle waarden in de TreeSetenextraheer de eerste k van hen:
openbare lijst findTopK (lijstinvoer, int k) {Set gesorteerdSet = nieuwe TreeSet (Comparator.reverseOrder ()); gesorteerdSet.addAll (invoer); retourneer gesorteerdeSet.stream (). limit (k) .collect (Collectors.toList ()); }De tijdscomplexiteit van deze oplossing is O (n * log n). Dit zou vooral efficiënter moeten zijn dan de brute-force-aanpak k ≥ log n.
Het is belangrijk om dat te onthouden TreeSet bevat geen duplicaten. Als gevolg hiervan werkt de oplossing alleen voor een invoerarray met verschillende waarden.
3.2. Prioriteits-rij
Prioriteits-rij is eenHoopdata structuur in Java. Met zijn hulp, we kunnen een O (n * log k) oplossing. Bovendien zal dit een snellere oplossing zijn dan de vorige. Vanwege het genoemde probleem, k is altijd kleiner dan de grootte van de array. Dus het betekent dat O (n * log k) ≤ O (n * log n).
Het algoritme itereert eenmaal door de opgegeven array. Bij elke iteratie voegen we een nieuw element toe aan de hoop. We houden ook de grootte van de hoop kleiner dan of gelijk aan k. We zullen dus extra elementen van de hoop moeten verwijderen en nieuwe moeten toevoegen. Als gevolg hiervan zal de heap, na het doorlopen van de array, de k grootste waarden:
openbare lijst findTopK (lijstinvoer, int k) {PriorityQueue maxHeap = nieuwe PriorityQueue (); input.forEach (nummer -> {maxHeap.add (nummer); if (maxHeap.size ()> k) {maxHeap.poll ();}}); Lijst topKList = nieuwe ArrayList (maxHeap); Collections.reverse (topKList); terug topKList; }4. Selectie-algoritme
Er zijn veel manieren om het gegeven probleem op te lossen. En hoewel het buiten het bestek van deze tutorial valt, met behulp van de selectie-algoritme-benaderingzal de beste zijn omdat het een lineaire tijdcomplexiteit oplevert.
5. Conclusie
In deze zelfstudie hebben we verschillende oplossingen beschreven om het k grootste elementen in een array.
Zoals gewoonlijk is de voorbeeldcode beschikbaar op GitHub.
