Wie finde ich k häufigste Elemente mit dem Java -Sammlungs -Framework?Java

Java-Forum
Anonymous
 Wie finde ich k häufigste Elemente mit dem Java -Sammlungs -Framework?

Post by Anonymous »

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 (

Code: Select all

entryList.sort()
) 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.

Quick Reply

Change Text Case: 
   
  • Similar Topics
    Replies
    Views
    Last post