Kth Largest Element in an Array
Ti viene dato un array di numeri interi nums e un numero intero k. Restituisci il valore più grande in posizione k in nums: il valore in posizione k, contando da 1, dopo aver ordinato l’array dal più grande al più piccolo.
I valori uguali si contano separatamente. In [5, 5, 1] il valore più grande è 5 e il secondo più grande è anch’esso 5.
Funzione
- numsinteger-array
- i valori da classificare
- kinteger
- quale valore più grande restituire, 1 per il più grande
- Restituisceinteger
- il k-esimo valore più grande, contando i duplicati
Vincoli
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104- Valori uguali contano come valori separati.
Esempi
- Input
- nums = [7, 2, 9, 4, 9, 1]k = 2
- Output
- 9
- Spiegazione
- Dal più grande al più piccolo, i valori sono
9, 9, 7, 4, 2, 1. I due 9 si contano separatamente, quindi il secondo più grande è9, non7.
- Input
- nums = [5, -3, 8, 0, 2]k = 4
- Output
- 0
- Spiegazione
- Dal più grande al più piccolo, i valori sono
8, 5, 2, 0, -3e il quarto è0.
- Input
- nums = [6]k = 1
- Output
- 6
- Spiegazione
- Con un solo valore e
k = 1, quel valore è il più grande.
+15 test nascosti all’invio
Per approfondire
Ora i valori arrivano uno alla volta. Riesci a indicare la mediana di tutti i valori visti finora dopo ogni arrivo, in O(log n) di tempo per valore?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Ordinata dal più grande al più piccolo, la risposta si trova in una posizione nota. Quale? E hai bisogno di tutti gli altri valori per conoscerla?
Il valore k-esimo più grande è il più piccolo tra i
kvalori più grandi. Se tieni solo ikvalori più grandi incontrati finora, quale di questi confronti con un nuovo valore?Mantieni un min-heap di al massimo
kvalori. Un nuovo valore sostituisce quello in cima quando è più grande, e alla fine la risposta è il valore in cima. Per un tempo medio diO(n), partiziona attorno a un pivot casuale come fa quicksort e mantieni solo il lato che contiene l’indicen-k.
Soluzione
Ordinare e leggere una posizione risponde alla domanda ed è abbastanza veloce in questo caso. Ciò che un intervistatore vuole vedere è quanto di quell’ordinamento riesci a evitare, perché ti serve una posizione, non tutte le n. Un min-heap di dimensione k conserva solo i valori che possono ancora essere la risposta, mentre quickselect partiziona come quicksort, ma segue solo il lato che contiene la risposta, riducendo così il tempo medio a O(n).
Ordina e leggi una posizione
Intuizione
Il valore k-esimo più grande è definito dall’ordine ordinato, quindi produci quell’ordine. Ordinato dal più grande al più piccolo, [7, 2, 9, 4, 9, 1] diventa [9, 9, 7, 4, 2, 1], e il k-esimo più grande si trova all’indice k-1. Per k = 2 si tratta dell’indice 1, il secondo 9. Se il tuo ordinamento mette prima il più piccolo, leggi invece l’indice n-k: l’indice 4 di [1, 2, 4, 7, 9, 9] è lo stesso 9.
I duplicati non richiedono una gestione speciale: l’ordinamento mantiene ogni copia e ogni copia occupa la propria posizione.
Con n = 10^4, un ordinamento esegue circa n log n ≈ 1.3 × 10^5 confronti, superando tutti i test. Lo spreco consiste nel mettere in ordine tutti gli n valori quando conta una sola posizione. I due approcci successivi fanno meno lavoro di questo tipo.
Algoritmo
- Copia
numsin modo che l'array del chiamante rimanga invariato. - Ordina la copia. Usa un confronto numerico; alcuni linguaggi confrontano i numeri come testo per impostazione predefinita.
- Restituisci l'indice
k-1in un ordinamento dal più grande al più piccolo, oppure l'indicen-kin un ordinamento dal più piccolo al più grande.
def findKthLargest(nums, k):
# Largest first: the k-th largest sits at index k-1.
ordered = sorted(nums, reverse=True)
return ordered[k - 1]Mantieni i k più grandi in un min-heap
Intuizione
Il valore più grande al k-esimo posto è il più piccolo tra i k valori più grandi. Quindi percorri nums una sola volta e mantieni, in un min-heap, solo i k valori più grandi incontrati fino a quel momento. La radice di un min-heap è il suo valore più piccolo, che è proprio il valore candidato come risposta.
Quando arriva un valore x e l'heap contiene meno di k valori, aggiungilo. Altrimenti confronta x con la radice. Se x non è maggiore, almeno k dei valori che hai mantenuto sono maggiori o uguali a x, quindi x non potrà mai essere la risposta e puoi saltarlo. Se x è maggiore, la radice è uscita dai k valori più grandi: sostituiscila con x. Nell'esempio 2, con k = 4, i primi quattro valori riempiono l'heap con 5, -3, 8, 0 e la radice è -3. Poi 2 supera -3 e lo sostituisce, la radice diventa 0 e 0 è la risposta.
Ogni valore richiede al massimo un'operazione sull'heap, che costa O(log k), quindi il costo totale è O(n log k) in termini di tempo e O(k) in termini di memoria. È più efficiente dell'ordinamento quando k è piccolo e funziona con un flusso di dati: non hai mai bisogno di avere tutti i valori contemporaneamente. Python ha heapq, Java PriorityQueue, C++ priority_queue con greater, Go container/heap, Rust BinaryHeap con Reverse e PHP SplMinHeap. Il codice per gli altri linguaggi implementa l'heap in un array, in cui i figli dell'indice i si trovano agli indici 2i+1 e 2i+2, oppure agli indici 2i e 2i+1 in Lua e R, che contano a partire da 1.
Algoritmo
- Inizia con un min-heap vuoto.
- Per ogni valore
x, aggiungilo finché l'heap contiene meno dikvalori. - Quando ne contiene
k, sostituisci l'elemento in cima conxsolo sexè maggiore dell'elemento in cima. - Dopo l'ultimo valore, restituisci l'elemento in cima all'heap.
import heapq
def findKthLargest(nums, k):
# A min-heap of the k largest values so far; its top is the smallest of them.
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
return heap[0]Quickselect con partizionamento a tre vie
Intuizione
Quicksort sceglie un pivot e partiziona: i valori più piccoli alla sua sinistra, quelli più grandi alla sua destra. Dopo una partizione, il pivot si trova al suo indice definitivo nell’array ordinato, anche se nessuno dei due lati è ancora ordinato. Quickselect sfrutta questo fatto. Nell’ordine dal più piccolo al più grande, la risposta si trova all’indice target = n-k. Dopo una partizione, target si trova a sinistra del pivot, sul pivot oppure a destra: quindi continui su un lato e scarti l’altro.
Per [7, 2, 9, 4, 9, 1] e k = 2, target è 6-2 = 4. Partiziona intorno a 4: 2 e 1 occupano gli indici 0 e 1, 4 occupa l’indice 2 e 7, 9, 9 occupano gli indici da 3 a 5. L’indice 4 si trova a destra, quindi mantieni solo gli indici da 3 a 5. Partiziona questi valori intorno a 9: 7 occupa l’indice 3 ed entrambi i 9 occupano gli indici 4 e 5. L’indice 4 contiene un 9, quindi la risposta è 9.
Usa una partizione a tre vie: prima i valori inferiori al pivot, poi quelli uguali e infine quelli superiori, individuati da lt e gt. Il blocco di valori uguali [lt, gt] si trova nella posizione corretta nell’array ordinato, quindi, se target rientra in questo blocco, hai finito. Con una semplice partizione a due vie, un array di 10^4 copie di 7 si riduce di un solo valore a ogni iterazione, per circa 5 × 10^7 passaggi; la versione a tre vie risolve il problema in un’unica passata.
Scegli il pivot a caso. La metà delle volte finisce nella metà centrale dell’intervallo, riducendolo a non più di tre quarti: il lavoro previsto corrisponde quindi a poche passate sui n valori, cioè O(n). Il caso peggiore è comunque O(n²) se ogni pivot è un valore estremo, e una scelta fissa come il primo elemento produce questo caso con un input già ordinato. Il codice opera su una copia, il che richiede O(n) di memoria; partizionare direttamente nums riduce il costo a O(1), se puoi modificare l’input.
Algoritmo
- Copia
numsina, impostatarget = n-k,lo = 0ehi = n-1. - Scegli un pivot casuale da
a[lo..hi]. - Partiziona
a[lo..hi]in valori minori, uguali e maggiori del pivot, lasciando i valori uguali ina[lt..gt]. - Se
target < lt, impostahi = lt-1; setarget > gt, impostalo = gt+1; altrimenti restituisci il pivot. - Ripeti dal passaggio 2.
import random
def findKthLargest(nums, k):
a = list(nums)
target = len(a) - k # the answer's index once a is sorted smallest first
lo, hi = 0, len(a) - 1
while True:
pivot = a[random.randint(lo, hi)]
# Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
# Now a[lt..gt] all equal pivot, and they are in their sorted places.
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
Trappole e casi limite
La maggior parte delle risposte errate deriva dai duplicati e dalla confusione tra i due modi di contare le posizioni.
- Rimuovere prima i duplicati. Il problema conta ogni copia: in
[7, 2, 9, 4, 9, 1]conk = 2la risposta è9, ma dopo aver trasformato l’array in un insieme diventa7. - Leggere l’indice sbagliato.
kconta a partire da 1, quindi la risposta si trova all’indicek-1in un ordinamento dal più grande al più piccolo e all’indicen-kin un ordinamento dal più piccolo al più grande, nonn-k-1. - Ordinare i numeri come testo. In JavaScript e TypeScript,
[10, 9, 2].sort()restituisce[10, 2, 9]. Passa(a, b) => a - b. - Usare un max-heap di dimensione
k. Rimuovendo il valore più grande si mantengono ikvalori più piccoli e si restituisce il k-esimo più piccolo. - Usare Quickselect con una partizione a due vie o un pivot fisso. Molti valori uguali o un array ordinato comportano un costo di
O(n²), caso incluso nei test di grandi dimensioni.
Domande frequenti4
Qual è la complessità temporale del k-esimo elemento più grande in un array?
L'ordinamento richiede un tempo O(n log n). Un min-heap di dimensione k richiede un tempo O(n log k) e una memoria O(k). Quickselect con un pivot casuale richiede in media un tempo O(n) e, nel caso peggiore, O(n²), evenienza molto improbabile con un pivot casuale.
Perché usare un min-heap, e non un max-heap, per trovare il k-esimo elemento più grande?
L'heap memorizza i k valori più grandi visti finora, e quello che devi confrontare ed espellere è il più piccolo tra questi. Un min-heap mantiene quel valore in cima. Un max-heap funziona solo se vi inserisci tutti gli n valori ed esegui il pop k-1 volte, cosa che richiede O(n) di memoria.
Dovrei usare un heap o quickselect per trovare il k-esimo elemento più grande?
Quickselect è più veloce in media, O(n), ma richiede che tutti i valori siano in memoria e li riordina. L'heap ha complessità O(n log k) senza casi pessimi, e funziona quando i valori arrivano uno alla volta e non puoi memorizzarli tutti. In un colloquio, spiega entrambi e implementa quello richiesto dalla domanda successiva.
È possibile trovare l’elemento più grande in posizione k in tempo lineare nel caso peggiore?
Sì. La regola della mediana delle mediane sceglie un pivot che garantisce di escludere una quota fissa dei valori, rendendo la selezione O(n) nel caso peggiore, anche se nella pratica è più lenta di un pivot casuale. Con valori limitati da -10^4 a 10^4, puoi anche contare quante volte si verifica ciascun valore e scorrere a ritroso partendo da 10^4 finché non hai superato k valori, in un tempo di O(n + 2 × 10^4).
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def findKthLargest(nums, k):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [7, 2, 9, 4, 9, 1] k = 2
Atteso
9