Algorithmen und Datenstrukturen · Middle · Frage 11 von 75
Wie findet man effizient die k größten Elemente eines großen Arrays?
- 1Einen Min-Heap der Größe k halten und seine Wurzel bei größerem Wert ersetzen
- 2Alle Elemente in ein
Setlegen und die ersten k nehmen - 3Bei jedem eintreffenden Wert das ganze Array absteigend sortieren
Antwort zeigen
Richtige Antwort: Einen Min-Heap der Größe k halten und seine Wurzel bei größerem Wert ersetzen
Erklärung
Der Heap hält immer die k größten bisher gesehenen Werte, und seine Wurzel ist der kleinste davon. Die Gesamtkosten sind O(n log k), was Sortieren (O(n log n)) bei kleinem k schlägt und auch mit Streams funktioniert.