Kth Largest Element in a Stream

Q: Perché usare un min-heap e non un max-heap per il k-esimo elemento più grande?

Il più piccolo dei k valori più grandi è sia la risposta sia il valore che un nuovo arrivato deve superare, e un min-heap di dimensione k lo mantiene in cima. Un max-heap contenente tutti i valori mette in cima il più grande, quindi per raggiungere il k -esimo bisogna estrarre k-1 valori e reinserirli a ogni nuovo arrivo.

Q: Qual è la complessità temporale di Kth Largest Element in a Stream?

Ogni elemento che arriva costa O(log k) : un confronto con il valore in cima e al massimo un riassestamento in un heap di k valori. Costruire l'heap a partire da nums costa O(n log k) , quindi l'intera esecuzione richiede tempo O((n + m) log k) e spazio aggiuntivo O(k) .

FacileHeap

+10

Un flusso di numeri interi inizia con i valori in nums. Poi i valori di adds arrivano uno alla volta. Dopo ogni arrivo, registra il valore più grande in kª posizione tra tutti quelli visti finora, contando separatamente i valori uguali. Restituisci i valori registrati nell'ordine, uno per ogni valore di adds.

nums contiene almeno k-1 valori, quindi dopo il primo arrivo ci sono sempre almeno k valori tra cui scegliere.

Funzione

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: la posizione da riportare, 1 per il valore più grande
numsinteger-array: i valori già presenti nel flusso
addsinteger-array: i valori che arrivano, in ordine
Restituisceinteger-array: il k-esimo valore più grande dopo ogni arrivo

Vincoli

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums può essere in qualsiasi ordine e i valori uguali vengono considerati valori distinti.

Esempi

Input: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Output: [3, 5, 6, 6, 7]
Spiegazione: Dopo 3 arriva il terzo più grande tra 7, 5, 3 e 1: è 3. Poi 9 lo porta a 5, 6 lo porta a 6, 2 non cambia nulla e 8 lo porta a 7 (9, 8, 7).

Input: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Output: [-2, 0, 0, 4]
Spiegazione: Con k = 1 la risposta è il valore più grande finora: -2 finché non arriva 0, rimane 0 dopo -1, poi 4.

Per approfondire

Come risponderesti alla stessa domanda se fosse possibile anche rimuovere valori dal flusso?

Suggerimenti

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

0 di 3 aperti

Soluzione

I valori non escono mai dallo stream, quindi un valore che scende al di sotto dell’attuale k-esimo più grande è escluso definitivamente. Mantieni solo i k valori più grandi in un min-heap: la sua cima è la risposta e ogni nuovo arrivo costa un confronto e al massimo un aggiornamento dell’heap O(log k).

Ordina dopo ogni arrivo

Corretto, ma non termina sui test più grandi

Intuizione

Mantieni ogni valore in una lista. Dopo ogni arrivo, ordinali in ordine crescente e leggi l’indice length-k, che per definizione corrisponde al k-esimo valore più grande.

A ogni arrivo ordini fino a n + m valori, dove n e m sono le lunghezze di nums e adds. Con 10^4 valori per ciascuna, si tratta di circa 2 × 10^9 confronti in totale.

Algoritmo

Copia nums in una lista values.
Per ogni valore di adds, aggiungilo a values.
Ordina values in ordine crescente e registra values[length-k].
Restituisci i valori registrati.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Heap minimo dei k valori più grandi

Intuizione

Una volta che un valore ha k valori più grandi sopra di sé, questo rimane vero per il resto del flusso, quindi contano solo i k valori più grandi visti finora. Memorizzali in un heap minimo. La sua cima è il più piccolo dei k valori più grandi, che è esattamente il k-esimo valore più grande in assoluto.

Quando arriva x e l'heap è pieno, confrontalo con la cima. Se x non è più grande, non è tra i k valori più grandi e non cambia nulla. Se è più grande, la cima viene rimossa: sostituiscila con x e fai scendere l'elemento, in O(log k). I valori iniziali seguono la stessa procedura, quindi nums può essere più lungo di k.

Nel primo esempio, dopo nums l'heap contiene 7, 1 e 5, con 1 in cima. L'arrivo di 3 sostituisce 1 e la cima, 3, è la prima risposta.

Algoritmo

Inizia con un min-heap vuoto.
Per aggiungere x: se l'heap contiene meno di k valori, inserisci x. Altrimenti, se x è maggiore del valore in cima, sostituisci il valore in cima con x e ripristina l'ordine dell'heap.
Aggiungi in questo modo ogni valore di nums.
Per ogni valore di adds, aggiungilo e registra il valore in cima all'heap.
Restituisci i valori registrati.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Trappole e casi limite

Eliminare i duplicati. I quattro valori più grandi tra 9, 6, 6, 6, 2 sono 9, 6, 6 e 6. Un insieme, oppure un controllo che salta i valori già presenti, restituisce 2 nel terzo esempio invece di 6.
Leggere la risposta prima di aggiungere. Quando nums contiene k-1 valori, l'heap è pieno solo dopo il primo inserimento: quindi aggiungi prima, poi leggi l'elemento in cima.
Contare dall'estremità sbagliata dopo un ordinamento. In ordine crescente, il k-esimo valore più grande si trova all'indice length-k; l'indice k-1 contiene il k-esimo valore più piccolo.
Usare l'ordine predefinito dell'heap. priority_queue di C++ e BinaryHeap di Rust sono max-heap: passa greater<int> oppure racchiudi i valori in Reverse.

Domande frequenti3

Perché usare un min-heap e non un max-heap per il k-esimo elemento più grande?

Il più piccolo dei k valori più grandi è sia la risposta sia il valore che un nuovo arrivato deve superare, e un min-heap di dimensione k lo mantiene in cima. Un max-heap contenente tutti i valori mette in cima il più grande, quindi per raggiungere il k-esimo bisogna estrarre k-1 valori e reinserirli a ogni nuovo arrivo.

Qual è la complessità temporale di Kth Largest Element in a Stream?

Ogni elemento che arriva costa O(log k): un confronto con il valore in cima e al massimo un riassestamento in un heap di k valori. Costruire l'heap a partire da nums costa O(n log k), quindi l'intera esecuzione richiede tempo O((n + m) log k) e spazio aggiuntivo O(k).

È possibile risolvere il problema del K-esimo elemento più grande in un flusso con una lista ordinata?

Sì. Mantieni tutti i valori ordinati, inserisci ogni nuovo arrivo al suo posto con la ricerca binaria e leggi il valore che si trova k posizioni dalla fine. La ricerca richiede O(log n), ma lo spostamento dei valori dopo il punto di inserimento richiede O(n) per ogni arrivo: circa 1.5 × 10^8 spostamenti per 10^4 valori iniziali e 10^4 arrivi.

def kthLargestStream(k, nums, adds):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Output atteso

[3, 5, 6, 6, 7]