Summary Ranges
Ricevi un array ordinato nums di numeri interi distinti. Suddividilo nel minor numero possibile di intervalli di numeri interi consecutivi, in modo che ogni valore appartenga esattamente a un intervallo. Scrivi un intervallo a..b come testo "a->b", oppure come "a" quando contiene un solo valore. Restituisci gli intervalli in ordine crescente.
Funzione
- numsinteger-array
- l'array ordinato di numeri interi distinti
- Restituiscestring-array
- gli intervalli come testo, dai valori più piccoli ai più grandi
Vincoli
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsè ordinato in ordine crescente e non contiene duplicati.
Esempi
- Input
- nums = [0, 1, 2, 5, 6, 9]
- Output
- ["0->2", "5->6", "9"]
- Spiegazione
0, 1, 2sono consecutivi, quindi formano"0->2". Il salto da 2 a 5 inizia un nuovo intervallo,"5->6", e 9 rimane da solo come"9".
- Input
- nums = [-3, -1, 0, 1, 4, 7, 8]
- Output
- ["-3", "-1->1", "4", "7->8"]
- Spiegazione
- -3 non ha un vicino (-2 manca),
-1, 0, 1formano una sequenza, 4 è isolato e7, 8chiudono la lista. I valori negativi funzionano allo stesso modo: dopo -1 viene -1 + 1 = 0.
+16 test nascosti all’invio
Per approfondire
Supponiamo che nums possa contenere duplicati, come [1, 2, 2, 3]. Cosa cambieresti affinché stampi comunque "1->3"?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
L’array è ordinato. Quando due valori adiacenti appartengono allo stesso intervallo?
Appartengono allo stesso intervallo esattamente quando
nums[i+1] == nums[i] + 1. Ogni altra coppia di vicini segna la fine di un intervallo e l’inizio del successivo.Ricorda dove è iniziato l'intervallo corrente. Procedi in avanti finché il valore successivo è uno in più di quello corrente; quando la sequenza si interrompe o l'array finisce, scrivi l'intervallo dal suo inizio al valore corrente e avvia l'intervallo successivo dal valore seguente.
Soluzione
Poiché i valori sono ordinati e distinti, un intervallo di numeri interi consecutivi è sempre una sequenza di elementi vicini nell’array, e un intervallo termina esattamente dove due elementi vicini differiscono di più di 1. Dividere l’array in corrispondenza di ogni intervallo vuoto produce il minor numero di intervalli, poiché nessun intervallo può attraversare un vuoto. Resta solo da tenere traccia con attenzione dell’inizio di ogni sequenza, dell’ultimo elemento e del formato del testo.
Controlla entrambi i vicini di ogni valore
Intuizione
Esamina un valore alla volta e poni due domande. Qui si apre un intervallo? Sì, quando è il primo valore oppure il valore precedente non è inferiore di uno. Qui si chiude un intervallo? Sì, quando è l’ultimo valore oppure il valore successivo non è superiore di uno.
In [0, 1, 2, 5, 6, 9], un intervallo si apre in corrispondenza di 0, 5 e 9 e si chiude in corrispondenza di 2, 6 e 9. Ricorda il valore in corrispondenza del quale si è aperto l’intervallo corrente. Quando un intervallo si chiude in corrispondenza di nums[i], scrivi "start->nums[i]", oppure solo "start" quando l’intervallo si è aperto e chiuso sullo stesso valore, come accade per 9.
Ogni valore viene visitato una volta e controlla due vicini, quindi il tempo è O(n). A parte l’output, tieni un solo valore iniziale in memoria, quindi lo spazio aggiuntivo è O(1).
Algoritmo
- Imposta
start = nums[0]. - Per ogni indice
i: sei > 0enums[i] != nums[i-1] + 1, impostastart = nums[i]. - Se
iè l'ultimo indice oppurenums[i+1] != nums[i] + 1, l'intervallo termina qui. - Aggiungi
"start"quandostart == nums[i], altrimenti"start->nums[i]". - Restituisci la lista dopo l'ultimo indice.
def summaryRanges(nums):
n = len(nums)
ranges = []
start = nums[0]
for i in range(n):
# A range opens where the value before is not one less.
if i > 0 and nums[i] != nums[i - 1] + 1:
start = nums[i]
# A range closes where the value after is not one more.
if i == n - 1 or nums[i + 1] != nums[i] + 1:
ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return rangesDue puntatori su ogni sequenza
Intuizione
Considera ogni intervallo come un blocco dell'array e individua i suoi due estremi. Il puntatore i si trova sul primo valore di un intervallo. Il puntatore j parte da i e si sposta verso destra finché il valore successivo è esattamente maggiore di uno, quindi si ferma sull'ultimo valore dell'intervallo.
Per [-3, -1, 0, 1, 4, 7, 8]: i su -3 non può estendersi, perché -1 non è -2, quindi l'intervallo è "-3". Poi i salta a -1 e j avanza oltre 0 e 1, fermandosi prima di 4: "-1->1". Poi "4" e "7->8". Dopo ogni intervallo, i si sposta a j+1, il primo valore del successivo.
Gli intervalli sono il minor numero possibile: due valori separati da un divario non possono mai appartenere allo stesso intervallo e il metodo divide solo in corrispondenza dei divari. Entrambi i puntatori avanzano soltanto, quindi il ciclo interno viene eseguito n volte in totale per tutti gli intervalli. Questo mantiene il tempo in O(n) e lo spazio aggiuntivo in O(1).
Algoritmo
- Imposta
i = 0. - Imposta
j = ie spostajverso destra mentrej+1 < nenums[j+1] == nums[j] + 1. - Aggiungi
"nums[i]"quandoi == j, altrimenti"nums[i]->nums[j]". - Imposta
i = j + 1e ripeti finchéinon supera la fine. - Restituisci la lista.
def summaryRanges(nums):
ranges = []
n = len(nums)
i = 0
while i < n:
# i is the first value of a run; push j to its last value.
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
# The next run starts right after this one.
i = j + 1
return ranges
Trappole e casi limite
La logica sta in poche righe; gli errori sono ai margini.
- Dimenticare l’ultimo intervallo. Un ciclo che scrive un intervallo solo quando incontra un’interruzione non scrive mai quello finale, quindi
[0, 1, 2, 5, 6, 9]perde il suo"9". Chiudi un intervallo anche all’ultimo indice. - Scrivere
"a->a"per un singolo valore. Un intervallo di un solo valore si scrive come"a". - Stampare i valori grandi in notazione scientifica. R converte un double come
1000000000in1e+09; converti i valori in numeri interi prima di incollarli.
Domande frequenti4
Qual è la complessità temporale di Summary Ranges?
O(n). Ogni valore viene visitato una volta e ogni intervallo viene scritto una volta. A parte la lista di output, lo spazio aggiuntivo è O(1): l'inizio dell'intervallo corrente e uno o due indici.
Perché tagliare in corrispondenza di ogni intervallo vuoto dà il minor numero di intervalli?
Un intervallo contiene numeri interi consecutivi, quindi non può contenere due valori separati da un numero mancante. Ogni lacuna nell'array ordinato deve quindi separare due intervalli e, con g lacune, servono almeno g+1 intervalli. Tagliando solo in corrispondenza delle lacune se ne ottengono esattamente g+1.
Come si gestisce un intervallo con un solo numero?
Controlla se l’intervallo inizia e termina con lo stesso valore. Se è così, scrivi solo quel valore, come "9". Altrimenti, scrivi l’inizio, la freccia e la fine, come "5->6". Con due puntatori, il controllo è i == j.
Gli intervalli di riepilogo richiedono che l’input sia ordinato?
Sì. Il metodo confronta solo gli elementi adiacenti, quindi si basa sul fatto che gli interi consecutivi si trovino uno accanto all’altro. Se l’input non è ordinato, ordinalo prima: l’intera operazione avrà complessità O(n log n). In alternativa, inserisci i valori in un insieme hash e amplia ogni intervallo a partire dal suo valore più piccolo, come nel problema della sequenza consecutiva più lunga.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def summaryRanges(nums):
# Scrivi il codice quiCaso 1
Caso 2
Input
nums = [0, 1, 2, 5, 6, 9]
Atteso
["0->2", "5->6", "9"]