Longest Consecutive Sequence
Ricevi un array di numeri interi nums in un ordine qualsiasi. 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 conta una sola volta.
Funzione
- numsinteger-array
- gli interi, in qualsiasi ordine, ripetizioni consentite
- 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, contiene 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 serie contiene un solo valore e la risposta è 1.
+17 test nascosti all’invio
Per approfondire
Supponiamo che i valori arrivino uno alla volta e che, dopo ciascuno, tu debba comunicare la sequenza più lunga fino a quel momento. 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 avanti. Quale domanda ripeti continuamente e quanto costa ogni risposta quando la cerchi nell’array?
La domanda è "c'è
x+1nell'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 percorso una sola volta.
Soluzione
I valori di una serie possono trovarsi in qualsiasi punto dell’array, quindi non puoi leggere le serie da sinistra a destra. L’ordinamento le dispone in O(n log n). Un insieme hash fa meglio: risponde a «qui c’è x+1?» in O(1) e, se conti solo a partire dai valori per cui manca x-1, ogni valore viene attraversato una sola volta, il che rende l’intera ricerca O(n).
Conta partendo da ogni valore, cercando nell'array
Corretto, ma non termina sui test più grandi
Intuizione
Considera ogni valore come un possibile inizio di una sequenza. Da x, cerca nell’array x+1; se c’è, cerca x+2 e continua finché manca un valore. Il numero di valori raggiunti è la sequenza che inizia da x e la lunghezza maggiore tra queste è la risposta.
È corretto perché ogni sequenza ha un valore minimo, quel valore si trova in nums e il ciclo lo prova come inizio e percorre tutta la sequenza. I duplicati non creano problemi: provano soltanto due volte lo stesso inizio.
È lento per due motivi. Ogni ricerca del tipo «è qui?» legge fino a n valori e una sequenza lunga viene percorsa di nuovo a partire da ciascuno dei suoi elementi. Prendi 10^4 valori che formano un’unica sequenza mescolata: i percorsi ammontano complessivamente a circa n²/2 = 5 × 10^7 passaggi e ogni passaggio scansiona in media metà dell’array. Si tratta di circa 2.5 × 10^11 confronti.
Algoritmo
- Imposta
besta 0. - Per ogni valore
startinnums, impostacurrentastartelengtha 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 sequenze
Intuizione
L'ordinamento mette uno accanto all'altro i valori di ogni serie. [40, 4, 39, 1, 3, 2, 41] diventa [1, 2, 3, 4, 39, 40, 41], e le serie si leggono da sinistra a destra: da 1 a 4, poi un salto a 39.
Scorri i valori ordinati e mantieni la lunghezza della serie corrente. Un valore di uno superiore al precedente la estende. Un valore uguale al precedente è una ripetizione: saltalo, perché non estende la serie né la conclude. Qualsiasi altro valore è un'interruzione e lì inizia una nuova serie di lunghezza 1.
L'ordinamento costa O(n log n) e la scansione O(n). Ordinare sul posto non richiede un array aggiuntivo, ma riordina l'input del chiamante; 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
Inserisci ogni valore in un insieme hash. Ora «x+1 è presente?» richiede in media O(1) invece di una scansione, e i duplicati si riducono a un’unica voce.
Partire da ogni valore ripeterebbe comunque del lavoro: nella sequenza 1, 2, 3, 4 faresti 3 passi partendo da 1, 2 da 2 e 1 da 3. Quindi inizia una scansione solo dal primo valore di una sequenza. Un valore x è il primo esattamente quando x-1 non è nell’insieme. In [40, 4, 39, 1, 3, 2, 41] solo 1 e 39 soddisfano questa condizione: partendo da 1 raggiungi 4, per una lunghezza di 4, e partendo da 39 raggiungi 41, per una lunghezza di 3.
Ogni valore appartiene esattamente a una sequenza, e solo la scansione che parte dal primo valore di quella sequenza lo attraversa, quindi tutte le scansioni insieme richiedono al massimo n passi. Aggiungi un controllo di appartenenza per ogni valore e la creazione dell’insieme, e il totale è O(n) in termini di tempo, con O(n) di memoria per l’insieme.
Scorri l’insieme, non nums. Se il primo valore di una sequenza di 2.500 valori compare 2.000 volte in nums, scorrere nums significa attraversare quella sequenza 2.000 volte.
Algoritmo
- Inserisci ogni valore di
numsin un insieme hashvaluese impostabestsu 0. - Per ogni valore
xnell'insieme, saltalo sex-1è nell'insieme: non è il primo valore della sua sequenza. - Altrimenti imposta
endsuxe incrementalo di 1 mentreend+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
La maggior parte delle risposte sbagliate è dovuta a valori ripetuti, mentre la maggior parte delle risposte lente è dovuta al percorrere la stessa sequenza più di una volta.
- Considerare una ripetizione come un’interruzione o come 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 nella scansione ordinata e aggiornarlo solo all’interno del ciclo. Un array con un solo valore restituisce quindi 0 invece di 1. - Percorrere l’insieme a partire da ogni valore, invece che solo dagli inizi delle sequenze. La risposta è corretta, ma una sequenza di
10^4valori richiede5 × 10^7passi: il lavoro quadratico che l’insieme avrebbe dovuto eliminare. - Eseguire un ciclo su
numsinvece che sull’insieme quando i valori si ripetono. La sequenza che inizia da un valore presente migliaia di volte viene percorsa migliaia di volte. - Contrassegnare i valori in un array indicizzato per valore. I valori arrivano a
±10^9, quindi l’array dovrebbe contenere2 × 10^9elementi.
Domande frequenti4
Qual è la complessità temporale della sequenza consecutiva più lunga?
La soluzione con un insieme hash richiede in media un tempo O(n) e usa memoria aggiuntiva O(n). Ordinare e poi contare le sequenze richiede un tempo O(n log n). Cercare nell’array ogni valore successivo senza un insieme richiede fino a O(n³).
Perché la soluzione con un insieme hash ha complessità O(n) anche se contiene un ciclo while all'interno di un ciclo for?
Il ciclo interno viene eseguito solo a partire da un valore il cui vicino a sinistra x-1 è assente, ovvero il primo valore della sua sequenza. Ogni valore viene saltato dal percorso della propria sequenza e da nessun altro percorso, quindi tutti i cicli interni insieme richiedono al massimo n passaggi. Il ciclo esterno aggiunge un controllo per ogni valore, per un totale di O(n).
Riesci a risolvere la sequenza consecutiva più lunga senza memoria aggiuntiva?
Sì, se puoi riordinare l’input: ordinalo sul posto e conta le sequenze in un’unica passata, saltando le ripetizioni. Questo usa memoria aggiuntiva O(1), ma richiede tempo O(n log n). La soluzione O(n) richiede l’insieme hash.
Può union-find risolvere la 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. Ha una complessità temporale vicina a O(n), ma richiede una mappa da valore a indice, collegamenti ai genitori e dimensioni, mentre la scansione dell'hash set svolge lo stesso compito con un solo insieme e due cicli.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def longestConsecutive(nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [40, 4, 39, 1, 3, 2, 41]
Atteso
4