Find Median from Data Stream

Q: Wie hoch ist die Zeitkomplexität von Find Median from Data Stream?

Mit zwei Heaps benötigt addNum O(log n) , höchstens drei Heap-Einfügungen oder -Entfernungen, und findMedian benötigt O(1) , also zwei Lesezugriffe. Jeder Wert wird gespeichert, daher beträgt der Speicherbedarf O(n) . Bei jeder Abfrage zu sortieren, kostet dagegen O(n log n) pro findMedian .

Q: Warum bewahrst du die Werte nicht in einem sortierten Array auf?

Ein sortiertes Array liefert die Antwort auf findMedian in O(1) , und die binäre Suche findet in O(log n) , an welcher Stelle ein neuer Wert eingefügt wird. Beim Einfügen werden jedoch alle Werte hinter dieser Stelle verschoben: O(n) pro addNum .

SchwerHeap

+10

Entwirf eine Struktur mit zwei Operationen: addNum speichert eine Ganzzahl, und findMedian gibt den Median aller bisher gespeicherten Werte zurück. Bei einer ungeraden Anzahl ist der Median der mittlere Wert; bei einer geraden Anzahl ist er der Durchschnitt der beiden mittleren Werte.

Operation i ist ops[i], wobei values[i] bei addNum die Zahl und bei findMedian 0 enthält. Führe sie der Reihe nach auf einer leeren Struktur aus und gib für jede Operation einen String zurück: "null" für addNum, den Median für findMedian. Gib den Median beispielsweise als "3", "2.5" oder "-0.5" aus: ohne Dezimalpunkt bei einer ganzen Zahl und null als "0", niemals als "-0".

Funktion

medianStreamOps(ops: string-array, values: integer-array) → string-array

opsstring-array: die Operationen in der Reihenfolge, in der sie ausgeführt werden
valuesinteger-array: die Zahl für jedes addNum, 0 für jedes findMedian
Gibt zurückstring-array: eine Antwort pro Operation, als Text

Einschränkungen

1 ≤ ops.length ≤ 3000
values.length == ops.length
Jedes ops[i] ist addNum oder findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ für addNum und values[i] == 0 für findMedian.
findMedian wird erst aufgerufen, nachdem mindestens ein addNum aufgerufen wurde.

Beispiele

Eingabe: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Ausgabe: ["null", "5", "null", "3", "null", "5", "null", "4"]
Erklärung: Bei 1 und 5 ist der Median (1 + 5) / 2 = 3. Bei 1, 5 und 8 ist er 5, und bei 1, 3, 5 und 8 ist er (3 + 5) / 2 = 4.

Weiterführende Frage

Wenn jeder Wert zwischen 0 und 100 läge, wie könntest du beide Operationen in konstanter Zeit ausführen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Der Median liegt zwischen den beiden Hälften der Daten, daher spielt die Reihenfolge innerhalb jeder Hälfte keine Rolle: Entscheidend sind nur der größte Wert der unteren Hälfte und der kleinste der oberen Hälfte. Zwei Heaps halten genau diese beiden Werte ganz oben. Jedes addNum kostet O(log n), und jedes findMedian liest in O(1) die beiden obersten Werte aus.

Bei jedem findMedian sortieren

Idee

Speichere jeden Wert in einer Liste. findMedian sortiert sie und liest die Indizes (total-1)/2 und total/2 mit ganzzahliger Division: Bei einer ungeraden Anzahl ist es derselbe Index, bei einer geraden Anzahl das mittlere Paar. Addiere die beiden Werte und halbiere die Summe, dann erhältst du in beiden Fällen den Median.

Halbiere mit Ganzzahlen. Eine gerade Summe lässt sich ohne Rest teilen. Eine ungerade Summe wird zu ihrer halbierten absoluten Größe gefolgt von .5, mit dem Vorzeichen der Summe, sodass -3 zu -1.5 wird.

Bei jeder Abfrage wird erneut sortiert. Bei 1,500 Hinzufügungen und einer Abfrage nach jeder sind das etwa 10^7 Vergleiche, während die Heaps nur einige zehntausend Schritte benötigen.

Algorithmus

Führe eine Liste values.
Für addNum x hänge x an und speichere "null".
Für findMedian sortiere values und addiere values[(total-1)/2] und values[total/2].
Halbiere die Summe als Text mit Ganzzahlen und speichere sie.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.values = []

    def addNum(self, x):
        self.values.append(x)

    def findMedian(self):
        self.values.sort()
        total = len(self.values)
        # For an odd count both indexes point at the one middle value.
        return half_text(self.values[(total - 1) // 2] + self.values[total // 2])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Zwei Heaps, die am Median geteilt werden

Idee

Teile die Werte in eine untere Hälfte low und eine obere Hälfte high auf, wobei jeder Wert in low höchstens so groß ist wie jeder Wert in high und low genauso viele Werte wie high oder einen mehr enthält. Der Median ist der größte Wert in low oder bei einer geraden Anzahl der Durchschnitt aus diesem Wert und dem kleinsten Wert in high. Ein Max-Heap für low und ein Min-Heap für high halten diese Werte oben.

Ein neuer Wert kommt in low, wenn er höchstens so groß ist wie der oberste Wert in low, andernfalls in high. Wenn die Größen auseinanderdriften, verschiebe einen obersten Wert von einer Hälfte in die andere: Er ist der Wert, der der anderen Hälfte am nächsten liegt, sodass die Reihenfolge erhalten bleibt. Ein Hinzufügen erfordert einige Heap-Operationen, O(log n), oder O(n) in R, wo der Heap bei jeder Änderung kopiert wird.

Nach den vier Hinzufügungen im ersten Beispiel enthält low die Werte 3 und 1 und high die Werte 5 und 8.

Algorithmus

Verwende einen Max-Heap low für die untere Hälfte und einen Min-Heap high für die obere Hälfte.
addNum x: Füge x zu low hinzu, wenn low leer ist oder x höchstens so groß wie das oberste Element ist, andernfalls zu high.
Wenn low zwei Werte mehr als high enthält, verschiebe das oberste Element von low nach high. Wenn high mehr Werte als low enthält, verschiebe das oberste Element von high nach low.
findMedian: Wenn low größer ist, gib dessen oberstes Element zurück. Andernfalls addiere die beiden obersten Elemente und halbiere die Summe mit Ganzzahldivision.

import heapq


def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.low = []   # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
        self.high = []  # the larger half, smallest on top

    def addNum(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low holds as many values as high, or one more.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return str(-self.low[0])
        return half_text(-self.low[0] + self.high[0])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Stolperfallen und Grenzfälle

Den Heap nach Größe statt nach Wert auswählen. Wird in den kleineren Heap eingefügt, ohne die Werte zu vergleichen, geht die Reihenfolge zwischen den beiden Hälften verloren, und die obersten Werte sind nicht mehr die mittleren Werte.
Die Halbierung mit einfacher Ganzzahldivision durchführen. In C und Java ist -1 / 2 gleich 0, daher ergibt das Anhängen von .5 für -0.5 die Ausgabe 0.5. In Python ist -3 // 2 gleich -2, wodurch für -1.5 die Ausgabe -2.5 entsteht. Gleitkommazahlen ergeben in manchen Sprachen die Ausgabe 3.0 oder 2.500000.
low in einem Min-Heap negiert speichern und vergessen, den Wert wieder zu negieren, wenn du das oberste Element ausliest oder einen Wert nach high verschiebst.
-0 schreiben. Die mittleren Werte -1 und 1 ergeben zusammen 0, und die Antwort lautet "0".

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Find Median from Data Stream?

Mit zwei Heaps benötigt addNum O(log n), höchstens drei Heap-Einfügungen oder -Entfernungen, und findMedian benötigt O(1), also zwei Lesezugriffe. Jeder Wert wird gespeichert, daher beträgt der Speicherbedarf O(n). Bei jeder Abfrage zu sortieren, kostet dagegen O(n log n) pro findMedian.

Warum bewahrst du die Werte nicht in einem sortierten Array auf?

Ein sortiertes Array liefert die Antwort auf findMedian in O(1), und die binäre Suche findet in O(log n), an welcher Stelle ein neuer Wert eingefügt wird. Beim Einfügen werden jedoch alle Werte hinter dieser Stelle verschoben: O(n) pro addNum.

Kannst du den exakten Median eines Datenstroms finden, ohne jeden Wert zu speichern?

Nicht generell. Jeder bisher gesehene Wert kann später zum Median werden, abhängig davon, was als Nächstes eintrifft. Daher werden für eine exakte Antwort alle Werte benötigt.

def medianStreamOps(ops, values):
    # Schreibe hier den Code

Test #1

Test #2

Argumente

ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
values = [5, 0, 1, 0, 8, 0, 3, 0]

Erwartete Ausgabe

["null", "5", "null", "3", "null", "5", "null", "4"]