Find Median from Data Stream

Q: Qual è la complessità temporale di Find Median from Data Stream?

Con due heap, addNum ha costo O(log n) , al massimo tre inserimenti o rimozioni dagli heap, e findMedian ha costo O(1) , due letture. Ogni valore viene memorizzato, quindi lo spazio è O(n) . Ordinare a ogni query costa invece O(n log n) per ogni findMedian .

Q: Perché non mantenere i valori in un array ordinato?

Un array ordinato restituisce la risposta a findMedian in O(1) , e la ricerca binaria trova dove inserire un nuovo valore in O(log n) . Ma inserirlo sposta ogni valore successivo a quel punto, O(n) per ogni addNum .

DifficileHeap

+10

Progetta una struttura con due operazioni: addNum memorizza un numero intero e findMedian restituisce la mediana di tutti i valori memorizzati fino a quel momento. La mediana di un numero dispari di valori è il valore centrale; per un numero pari è la media dei due valori centrali.

L’operazione i è ops[i], con values[i] che contiene il numero per un’operazione addNum e 0 per un’operazione findMedian. Esegui le operazioni in ordine su una struttura vuota e restituisci una stringa per ciascuna: "null" per addNum, la mediana per findMedian. Scrivi la mediana come "3", "2.5" o "-0.5": nessun separatore decimale per un numero intero e zero come "0", mai "-0".

Funzione

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

opsstring-array: le operazioni, nell'ordine in cui vengono eseguite
valuesinteger-array: il numero per ogni addNum, 0 per ogni findMedian
Restituiscestring-array: una risposta per operazione, sotto forma di testo

Vincoli

1 ≤ ops.length ≤ 3000
values.length == ops.length
Ogni ops[i] è addNum o findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ per addNum e values[i] == 0 per findMedian.
findMedian viene chiamata solo dopo almeno una addNum.

Esempi

Input: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Output: ["null", "5", "null", "3", "null", "5", "null", "4"]
Spiegazione: Con 1 e 5 la mediana è (1 + 5) / 2 = 3. Con 1, 5 e 8 è 5, e con 1, 3, 5 e 8 è (3 + 5) / 2 = 4.

Per approfondire

Se ogni valore fosse compreso tra 0 e 100, come potresti fare in modo che entrambe le operazioni vengano eseguite in tempo costante?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La mediana si trova tra le due metà dei dati, quindi l’ordine all’interno di ciascuna metà non è importante: contano solo il valore più grande della metà inferiore e il valore più piccolo di quella superiore. Due heap mantengono esattamente questi due valori in cima. Ogni addNum ha un costo di O(log n) e ogni findMedian legge i due valori in cima in O(1).

Ordina a ogni findMedian

Intuizione

Memorizza ogni valore in una lista. findMedian la ordina e legge gli indici (total-1)/2 e total/2, con divisione intera: lo stesso indice per un numero dispari, la coppia centrale per un numero pari. Somma i due valori e dimezza la somma, e ottieni la mediana in entrambi i casi.

Dimezza usando numeri interi. Una somma pari si divide esattamente. Una somma dispari diventa la metà del suo valore assoluto seguita da .5, con il segno della somma, quindi -3 diventa -1.5.

Ogni query ordina di nuovo. Con 1,500 aggiunte e una query dopo ciascuna, si tratta di circa 10^7 confronti, mentre gli heap richiedono qualche decina di migliaia di passaggi.

Algoritmo

Mantieni un elenco values.
Per addNum x, aggiungi x e registra "null".
Per findMedian, ordina values e aggiungi values[(total-1)/2] e values[total/2].
Dimezza la somma come testo con numeri interi e registrala.

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

Due heap divisi in corrispondenza della mediana

Intuizione

Dividi i valori in una metà inferiore low e una metà superiore high, in modo che ogni valore di low sia al massimo pari a ogni valore di high e che low abbia la stessa dimensione di high o un elemento in più. La mediana è il valore più grande di low oppure, se il numero di valori è pari, la media tra questo e il valore più piccolo di high. Un max-heap per low e un min-heap per high mantengono questi valori in cima.

Un nuovo valore viene inserito in low se è minore o uguale al valore in cima a low, altrimenti in high. Quando le dimensioni si sbilanciano, sposta un valore in cima da una metà all’altra: è il valore più vicino all’altra metà, quindi l’ordine viene mantenuto. Un’aggiunta richiede poche operazioni sull’heap, O(log n), oppure O(n) in R, che copia l’heap a ogni modifica.

Dopo le quattro aggiunte del primo esempio, low contiene 3 e 1 e high contiene 5 e 8.

Algoritmo

Mantieni un max-heap low per la metà inferiore e un min-heap high per quella superiore.
addNum x: inserisci x in low se low è vuoto o se x è al massimo pari al suo elemento in cima; altrimenti inseriscilo in high.
Se low contiene due valori in più rispetto a high, sposta l'elemento in cima a low in high. Se high contiene più valori di low, sposta l'elemento in cima a high in low.
findMedian: se low è più grande, registra il suo elemento in cima. Altrimenti somma i due elementi in cima e dividi la somma per due usando la divisione intera.

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

Trappole e casi limite

Scegliere l'heap in base alla dimensione invece che al valore. Inserire elementi nell'heap più piccolo senza confrontarli rompe l'ordine tra le due metà e gli elementi in cima non sono più i valori centrali.
Dividere per due usando la divisione intera semplice. In C e Java -1 / 2 è 0, quindi aggiungere .5 stampa 0.5 per -0.5. In Python -3 // 2 è -2, quindi stampa -2.5 per -1.5. In alcuni linguaggi la virgola mobile stampa 3.0 o 2.500000.
Memorizzare low con il segno invertito in un min-heap e dimenticare di invertirlo di nuovo quando se ne legge l'elemento in cima o si sposta un valore in high.
Scrivere -0. I valori centrali -1 e 1 hanno somma 0 e la risposta è "0".

Domande frequenti3

Qual è la complessità temporale di Find Median from Data Stream?

Con due heap, addNum ha costo O(log n), al massimo tre inserimenti o rimozioni dagli heap, e findMedian ha costo O(1), due letture. Ogni valore viene memorizzato, quindi lo spazio è O(n). Ordinare a ogni query costa invece O(n log n) per ogni findMedian.

Perché non mantenere i valori in un array ordinato?

Un array ordinato restituisce la risposta a findMedian in O(1), e la ricerca binaria trova dove inserire un nuovo valore in O(log n). Ma inserirlo sposta ogni valore successivo a quel punto, O(n) per ogni addNum.

Riesci a trovare la mediana esatta di un flusso senza memorizzare ogni valore?

Non in generale. Qualsiasi valore visto finora può diventare la mediana in seguito, a seconda di cosa arriva dopo, quindi per una risposta esatta servono tutti.

def medianStreamOps(ops, values):
    # Scrivi il codice qui

Test #1

Test #2

Argomenti

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

Output atteso

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