Ich habe eine Frage gelesen und suche nach Informationen zur Lösung:
Zahlen werden zufällig generiert und in einem (expandierenden) Array gespeichert. Wie würden Sie den Median verfolgen?
Es gibt zwei Datenstrukturen, die das Problem lösen können. Einer ist der ausgeglichene Binärbaum, der andere sind zwei Haufen, die die größte Hälfte und die kleinste Hälfte der Elemente verfolgen. Ich denke, diese beiden Lösungen haben die gleiche Laufzeit wie O(n lg n), bin mir aber meines Urteils nicht sicher.
Was ist der beste Weg, um den Median zu verfolgen?
Mein Versuch:
In dieser Frage ， Ich denke, ein Haufen ist der beste Weg, um den Median zu verfolgen. Es gibt zwei Haufen, den großen und den kleinen Haufen, die nicht sequentiell sein müssen. Zunächst berechnen wir den Mittelwert der Elemente im Array. Wenn das Element kleiner als der Mittelwert ist, setzen wir die Zahl auf den kleinen Haufen. Im Gegenteil, wir setzen die Nummer auf den großen Haufen. Wenn die Anzahl des großen Haufens gleich der Anzahl des kleinen Haufens ist, ist der größte im kleinen und der kleinste im großen Haufen der Median. Wenn die beiden Heaps unterschiedliche Größen haben, wird das Stammelement einfach aus dem Heap mit der größeren Größe entfernt und an die Wurzel des kleineren Heaps verschoben. Bei großen Heaps ist das Root-Element das kleinste und bei kleinen Heaps das Root-Element das größte. Auf diese Weise, wenn die beiden Haufen die gleiche Größe oder einen digitalen Unterschied haben,
Ich denke, diese Lösung hat die Laufzeit als O (m * n), m bedeutet die Zeiten, zu denen wir die Unwuchthaufen anpassen.
Ist dies der beste Weg, um den Median zu verfolgen?
quelle
std::nth_elementjemand?Antworten:
Es gibt wahrscheinlich mehr als 2 Datenstrukturen, die dieses Problem lösen. Sehen Sie sich ungefähre Mediane und andere Quantile in einem Durchgang und mit begrenztem Speicher an
Sie benutzen keine zwei Haufen. Ich stelle mir vor, Sie könnten ihren Algorithmus ändern, um regelmäßig einen ungefähren Medianwert zu erhalten. Wie gut eine Annäherung sein würde, hängt natürlich von vielen Faktoren ab, nicht zuletzt davon, wie viele Daten den Algorithmus durchlaufen haben.
quelle
Eine bessere Lösung ist die Verwendung einer Überspringliste. Da die Liste, in die Sie einfügen möchten, immer als sortierte Liste verwaltet wird (aufgrund der Art und Weise, wie Sie sie erstellen), ist die Komplexität des Einfügens O (log n). Sie werden die Tatsache ausnutzen, dass Sie beim ersten Einfügen den Median zu Nullkosten erhalten (das eingefügte Element ist der Median). Nach jeder weiteren Einfügung wird Ihre Liste weiterhin sortiert, und der Median selbst wird um einen einzelnen Index nach oben oder unten verschoben, und dieser Vergleich ist O (1).
Gesamtkomplexität = O (log n)
quelle
O(log n)- das Einfügen von n Elementen hat eine Komplexität vonO(n log n)Tatsächlich können Sie den Median in O (n) -Operationen nur finden, indem Sie die k - kleinste Zahl in einer Liste finden. Weitere Informationen finden Sie im Auswahlalgorithmus für den Median der Mediane .
quelle