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.
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]
}
}
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.