Algorithmen und Datenstrukturen · Senior · Frage 56 von 75
Wie hält man den laufenden Median eines Streams effizient?
- 1In ein sortiertes Array einfügen und die Mitte lesen
- 2Den laufenden Durchschnitt halten, der dem Median entspricht
- 3Ein Max-Heap für die untere Hälfte, ein Min-Heap für die obere
Antwort zeigen
Richtige Antwort: Ein Max-Heap für die untere Hälfte, ein Min-Heap für die obere
Erklärung
Halte die Heaps gleich groß; der Median ist eine der Wurzeln oder ihr Mittelwert. Jedes Einfügen ist O(log n). Ein sortiertes Array braucht pro Einfügen O(n) Verschiebung, und der Durchschnitt ist nicht der Median.