Wie finde ich k häufigste Elemente mit dem Java -Sammlungs -Framework?
Posted: 02 Feb 2025, 08:06
Ich habe eine Reihe von Ganzzahlen und muss die häufigsten Elemente effizient finden. Die Lösung sollte idealerweise in o (N log k) Zeitkomplexität mit Java -Sammlungen funktionieren. Das Sortieren aller Elemente benötigt o (n log n) , was ineffizient ist, wenn n groß ist. Ich suche einen optimierteren Ansatz. Hashmap Um die Frequenz jedes Elements zu zählen. Dann habe ich die Einträge mit collectionss.sort () sortiert, aber dieser Ansatz läuft in o (n log n) , was nicht optimal ist. Ich habe mithilfe von PriorityQueue (Minheap) oder Treemap untersucht, aber ich kämpfe damit, sie richtig umzusetzen. Insbesondere bin ich mir nicht sicher, wie Sie die häufigsten Elemente effizient beibehalten können, während ich die Frequenzkarte iteriere.
Problem mit diesem Code:
Der Sortierschritt (Sortierschritt () nimmt o (n log n) , was für große n ineffizient ist. Anstatt zu sortieren, glaube ich, dass die Verwendung eines minheap (priorityQueue) oder treemap die Leistung verbessern kann. Lösungen, fanden jedoch hauptsächlich Sammlungen. Einige Beiträge schlagen vor, einen Mindeap zu verwenden, aber ich kämpfe mit der Aufrechterhaltung der richtigen Haufenstruktur, während ich über die Karte iteriere.
Code: Select all
import java.util.*;
public class KMostFrequent {
public static List topKFrequent(int[] nums, int k) {
Map frequencyMap = new HashMap();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
List entryList = new ArrayList(frequencyMap.entrySet());
entryList.sort((a, b) -> b.getValue() - a.getValue()); // Sorting in descending order
List result = new ArrayList();
for (int i = 0; i < k; i++) {
result.add(entryList.get(i).getKey());
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 1, 1, 2, 2, 3};
int k = 2;
System.out.println(topKFrequent(nums, k)); // Expected Output: [1, 2]
}
}
Der Sortierschritt (Sortierschritt (
Code: Select all
entryList.sort()