Longest Consecutive Sequence
Ti viene fornito un array di interi nums senza un ordine particolare. Una sequenza consecutiva è un gruppo di valori x, x+1, x+2 e così via, ognuno dei quali compare da qualche parte in nums. Restituisci la lunghezza della sequenza consecutiva più lunga. Un valore che compare più di una volta viene conteggiato una sola volta.
Funzione
- numsinteger-array
- gli interi, in qualsiasi ordine, con ripetizioni ammesse
- Restituisceinteger
- la lunghezza della sequenza più lunga di valori consecutivi presenti in nums
Vincoli
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- I valori possono ripetersi. Le posizioni nell'array non contano, conta solo quali valori sono presenti.
Esempi
- Input
- nums = [40, 4, 39, 1, 3, 2, 41]
- Output
- 4
- Spiegazione
1,2,3e4sono tutti presenti, una serie di 4, anche se sono sparsi nell'array. L'altra serie, da39a41, ha solo 3 valori.
- Input
- nums = [7, 3, 7, 5, 6, 5]
- Output
- 3
- Spiegazione
5,6e7formano una sequenza di 3. Il secondo7e il secondo5non aggiungono nulla, e3non può unirsi perché manca4.
- Input
- nums = [10, 30, 20]
- Output
- 1
- Spiegazione
- Non ci sono due valori che differiscono di 1, quindi ogni sequenza contiene un solo valore e la risposta è 1.
Per approfondire
Supponiamo che i valori arrivino uno alla volta e che dopo ciascuno tu debba indicare la serie più lunga finora. Riesci a mantenere aggiornata la risposta in tempo medio O(1) per valore?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Prova ogni valore come primo numero di una sequenza e conta in ordine crescente. Quale domanda fai più e più volte e quanto costa ogni risposta quando lo cerchi nell’array?
La domanda è «
x+1è nell’array?». Un insieme hash risponde in tempo costante in media e rimuove anche i duplicati.Inizia a contare solo da un valore
xil cuix-1non è presente nell’insieme. Da lì, procedi conx+1,x+2e così via finché l’insieme li contiene, e conserva il percorso più lungo. Ogni valore viene quindi attraversato da un solo percorso.
Soluzione
I valori di una sequenza possono trovarsi in qualsiasi posizione dell’array. L’ordinamento li dispone in O(n log n). Un insieme hash risponde alla domanda «è presente x+1?» in O(1) e, se conti solo a partire dai valori per cui manca x-1, ogni valore viene percorso una sola volta: O(n) in totale.
Conta in avanti a partire da ogni valore cercando nell'array
Corretto, ma non termina sui test più grandi
Intuizione
Considera ogni valore come il possibile inizio di una sequenza. A partire da x, cerca nell’array x+1, poi x+2, finché manca un valore, e conserva il conteggio più alto. Ogni sequenza ha un valore minimo in nums e il ciclo la percorre tutta a partire da quel valore.
Ogni ricerca legge fino a n valori e una sequenza lunga viene percorsa di nuovo a partire da ogni suo elemento. Per 10^4 valori che formano un’unica sequenza mescolata, le scansioni richiedono circa n²/2 = 5 × 10^7 passaggi, ciascuna esaminando in media metà dell’array: circa 2.5 × 10^11 confronti.
Algoritmo
- Imposta
bestsu 0. - Per ogni valore
startinnums, impostacurrentsustartelengthsu 1. - Mentre una scansione di
numstrovacurrent+1, aggiungi 1 acurrente alength. - Memorizza
lengthinbestse è maggiore. - Restituisci
best.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return bestOrdina, poi conta le serie
Intuizione
L'ordinamento mette i valori di ogni sequenza uno accanto all'altro: [40, 4, 39, 1, 3, 2, 41] diventa [1, 2, 3, 4, 39, 40, 41], e le sequenze si leggono da sinistra a destra.
Scorri i valori ordinati e tieni traccia della lunghezza della sequenza corrente. Un valore maggiore di uno rispetto al precedente la estende. Un valore ripetuto non estende né termina la sequenza, quindi saltalo. Qualsiasi altro valore avvia una nuova sequenza di lunghezza 1.
L'ordinamento ha un costo di O(n log n) e la scansione di O(n). Ordinare sul posto non richiede un array aggiuntivo; i linguaggi che ordinano una copia usano O(n) di memoria.
Algoritmo
- Ordina
numsin ordine crescente. - Imposta
besteruna 1, poiché l'array non è mai vuoto. - Per ogni indice
ia partire da 1, saltanums[i]se è uguale anums[i-1]. - Se
nums[i]ènums[i-1]+1, aggiungi 1 arun; altrimenti impostaruna 1. Memorizzaruninbestse è maggiore. - Restituisci
best.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestInsieme hash, contando solo dall'inizio di ogni esecuzione
Intuizione
Con ogni valore in un insieme hash, un controllo di appartenenza costa in media O(1) e i duplicati vengono accorpati in un'unica voce.
Partire da ogni valore ripeterebbe comunque il lavoro: nella sequenza 1, 2, 3, 4 faresti 3 passi a partire da 1, 2 da 2 e 1 da 3. Quindi cammina solo a partire dal primo valore di una sequenza, che è esattamente un valore x per cui manca x-1. Nell'esempio 1 solo 1 e 39 soddisfano questa condizione, formando sequenze di 4 e 3.
Ogni valore appartiene a una sola sequenza e viene percorso solo dalla camminata di quella sequenza, quindi tutte le camminate insieme richiedono al massimo n passi. Con un controllo per ogni valore, il totale è di O(n) in termini di tempo e O(n) in termini di memoria per l'insieme.
Algoritmo
- Inserisci ogni valore di
numsin un insieme hashvaluese impostabesta 0. - Per ogni valore
xnell’insieme, saltalo sex-1è nell’insieme: non è il primo valore della sua sequenza. - Altrimenti imposta
endsuxe incrementalo di 1 finchéend+1è nell’insieme. - Memorizza
end-x+1inbestse è maggiore. - Restituisci
best.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
Trappole e casi limite
- Considerare un numero ripetuto come un intervallo o un passo dopo l’ordinamento. In
[1, 2, 2, 3], azzerare la sequenza al secondo2dà 2, mentre contarlo come un passo dà 4. La risposta è 3. - Inizializzare
besta 0 durante l’attraversamento ordinato e aggiornarlo solo all’interno del ciclo. Un array con un solo valore restituisce quindi 0 invece di 1. - Partire da ogni valore dell’insieme invece che solo dall’inizio delle sequenze. Una singola sequenza di
10^4valori richiede quindi5 × 10^7passi. - Iterare su
numsinvece che sull’insieme. Se il primo valore di una sequenza di 2,500 elementi compare 2,000 volte, la sequenza viene percorsa 2,000 volte. - Usare i valori come indici di un array. I valori arrivano a
±10^9, quindi servono2 × 10^9elementi.
Domande frequenti3
Qual è la complessità temporale della sequenza consecutiva più lunga?
La soluzione con un insieme hash ha una complessità temporale media di O(n) e richiede O(n) di memoria aggiuntiva. L’ordinamento e il conteggio dei blocchi richiedono O(n log n). Cercare nell’array ogni valore successivo senza un insieme richiede fino a O(n³).
Riesci a risolvere il problema della sequenza consecutiva più lunga senza memoria aggiuntiva?
Sì, se puoi riordinare l’input: ordinalo sul posto e conta le sequenze in un unico passaggio, ignorando le ripetizioni. Questo richiede memoria aggiuntiva O(1), ma tempo O(n log n). La soluzione O(n) richiede l’insieme hash.
Union-find può risolvere il problema della sequenza consecutiva più lunga?
Sì. Crea un insieme per ogni valore distinto, unisci x con x+1 ogni volta che sono presenti entrambi e restituisci la dimensione dell'insieme più grande. Viene eseguito in un tempo vicino a O(n), ma richiede una mappa dei valori con i rispettivi indici, collegamenti ai genitori e dimensioni, mentre l'iterazione sull'insieme hash richiede un solo insieme.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def longestConsecutive(nums):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
nums = [40, 4, 39, 1, 3, 2, 41]
Output atteso
4