progettare una coda che supporta la funzione getMedian

Question

Questa è una domanda di intervista. È necessario progettare una coda che contiene valori interi e ha una funzione getMedian() che restituisce l'elemento mediano della coda corrente. Puoi usare O (n) spazio extra.

Può getMedian() essere implementato con la complessità temporale < O (n)?

Per esempio: Quando la coda ha i seguenti valori (2, 1, 2, 2, 6, 4, 2, 5) , questo metodo restituisce 2 e non rimuove l'oggetto.

Answer 1

L'implementazione noto per il vostro problema è il modo:

Quello che è necessario implementare è 2 mucchi, uno sarà un min-heap e l'altro un max-heap.
Inoltre, è necessario un numero intero per dirci il numero di oggetti nella coda.

I vincoli per i mucchi sono i seguenti:
1. Il min-heap avranno gli oggetti più grandi della coda
2. Il max-heap avrà gli oggetti più piccoli della coda
3. Il max-heap avrà lo stesso o 1 oggetto in più del min-heap

In questo modo, se si dispone di un numero dispari di oggetti, la mediana sarebbe esattamente l'oggetto massimo nel max-heap. Se hai un numero pari di oggetti, la tua mediana sarebbe la media di entrambe le radici dei tuoi heap (max di max-heap, min di min-heap).

È importante notare che se gli heap diventano irregolari, ad esempio se si "pop" da un determinato heap, sarà necessario rimuovere dall'altro heap e spostarlo. Ma questo non è un problema in quanto tutto ciò di cui hai bisogno sono le radici dei tuoi heap e niente di più.

La complessità momento della getMedian diventa O (1)

appena trovato un articolo sul tema: link

risposta al commento

Il max-heap detiene la metà più piccolo elementi.
Quando si aggiunge un nuovo numero alla coda, si controlla innanzitutto qual è il numero di oggetti nella coda.
se il numero che si sta aggiungendo è un numero pari, significa che deve essere aggiunto al max-heap in quanto entrambe le code hanno la stessa dimensione.
Si vede quindi quale è il massimo nel max-heap.
Se è più grande del tuo numero, puoi semplicemente inserirlo nel max-heap.
se è più piccolo, significa che il nuovo numero potrebbe essere più grande di un numero nel min-heap.
in modo da vedere qual è il minimo nel min-heap.
se il numero è minore del minimo, che è possibile inserirlo nel max-heap, se è più grande, quindi si sposta il min nel min-heap sul max-heap e si inserisce il nuovo numero nel min-heap.
Se il numero è un numero dispari, è necessario aggiungerlo al min-heap poiché il max-heap ne ha uno in più, e così via ..

E 'un po' complicato, ma se non ancora capire Non mi occupo di pseudo codifica per voi