Top K Frequent Elements

Prima conta. Un solo passaggio con una mappa hash dai valori ai conteggi trasforma [4, 1, 4, 2, 1, 4, 3, 1, 4] in 4 → 4, 1 → 3, 2 → 1, 3 → 1.

Poi disponi i valori distinti nell’ordine della risposta: prima il conteggio più alto e, a parità di conteggio, prima il valore più piccolo. Fornisci all’ordinamento esattamente questo criterio di confronto, usando il conteggio come prima chiave e il valore come seconda; le prime k voci dell’elenco ordinato sono la risposta. In questo caso l’ordine è 4, 1, 2, 3 e k = 2 mantiene 4 e 1.

Il conteggio costa O(n). Ordinare i d valori distinti costa O(d log d), al massimo O(n log n) quando tutti i valori sono diversi: 10^4 valori richiedono circa 1.3 × 10^5 confronti, un’operazione rapida. Lo svantaggio è che l’ordinamento ordina tutti i valori, mentre ne servono solo i primi k.

Ti servono solo i k valori migliori, quindi conserva solo k candidati. Per ogni nuovo valore, la domanda è se supera il candidato più debole che conservi, dove «più debole» significa con un conteggio inferiore, oppure con lo stesso conteggio e un valore maggiore. Un min-heap ordinato secondo questa regola mantiene in cima il candidato più debole, che puoi leggere in O(1) e sostituire in O(log k).

Esamina i valori distinti. Finché l’heap contiene meno di k valori, aggiungi il valore. In seguito, un valore che supera quello in cima lo sostituisce, mentre un valore che non lo supera viene scartato, perché sono già conservati k valori migliori. Con un heap di libreria, è più breve inserire ogni valore ed estrarne uno ogni volta che l’heap supera k, mantenendo così gli stessi k valori.

Alla fine l’heap contiene la risposta, ma non nell’ordine desiderato: un heap è ordinato solo parzialmente. L’estrazione restituisce prima il valore più debole, quindi scrivi la risposta dalla posizione finale a quella iniziale.

Ognuno degli d valori distinti richiede al massimo un’operazione sull’heap con k elementi, quindi la selezione richiede O(d log k). È più efficiente dell’ordinamento quando k è molto più piccolo di d, per esempio per trovare i primi 10 tra 8000 valori distinti.

Un conteggio non è un numero qualsiasi: è un numero intero compreso tra 1 e n. Questo permette di usare il bucket sort. Crea un bucket per ogni conteggio: il bucket c contiene i valori che compaiono esattamente c volte; poi leggi i bucket dal bucket n verso il basso. I valori escono in ordine di frequenza decrescente e non si confrontano mai due conteggi.

La regola per i pareggi richiede un'altra cosa: all'interno di un bucket, il valore più piccolo deve venire prima. I valori sono compresi tra -10^4 e 10^4, quindi un array di R = 2 × 10^4 + 1 contatori può eseguire il conteggio, con il valore v all'indice v + 10^4. Scorri l'array dal valore più piccolo al più grande e aggiungi ogni valore al bucket corrispondente al suo conteggio. Ogni bucket si riempie in ordine crescente, che è l'ordine richiesto per i pareggi, quindi non serve mai ordinare.

Per [5, -2, 7, -2, 7, 5, 9], la scansione inserisce -2, 5, 7 nel bucket 2, in quest'ordine, e 9 nel bucket 1. Leggendo a ritroso dal bucket 7, il primo bucket non vuoto è il bucket 2 e k = 2 prende -2 e 5.

Il lavoro consiste in un passaggio su nums, un passaggio sui R contatori e un passaggio sui bucket, per un totale di O(n + R): lineare per un intervallo fisso di valori. Con una mappa hash al posto dell'array di conteggio, il conteggio resta lineare, ma i bucket si riempiono nell'ordine della mappa e dovresti ordinare ciascuno per rispettare la regola dei pareggi.