Summary Ranges
Você recebe um array ordenado nums de números inteiros distintos. Divida-o no menor número possível de intervalos de números inteiros consecutivos, de modo que cada valor pertença a exatamente um intervalo. Escreva um intervalo a..b como o texto "a->b", ou como "a" quando ele contiver um único valor. Retorne os intervalos em ordem crescente.
Função
- numsinteger-array
- o array ordenado de números inteiros distintos
- Retornastring-array
- os intervalos como texto, dos menores valores aos maiores
Restrições
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsestá ordenado em ordem crescente e não tem duplicatas.
Exemplos
- Entrada
- nums = [0, 1, 2, 5, 6, 9]
- Saída
- ["0->2", "5->6", "9"]
- Explicação
0, 1, 2vêm em sequência, então formam"0->2". O salto de 2 para 5 inicia um novo intervalo,"5->6", e 9 fica sozinho como"9".
- Entrada
- nums = [-3, -1, 0, 1, 4, 7, 8]
- Saída
- ["-3", "-1->1", "4", "7->8"]
- Explicação
- -3 não tem vizinho (-2 está faltando),
-1, 0, 1formam uma sequência, 4 fica sozinho, e7, 8fecham a lista. Os valores negativos funcionam da mesma maneira: depois de -1 vem -1 + 1 = 0.
+16 testes ocultos ao enviar
Para ir além
Suponha que nums pudesse conter duplicatas, como [1, 2, 2, 3]. O que você mudaria para que ainda imprimisse "1->3"?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
O array está ordenado. Quando dois valores vizinhos pertencem ao mesmo intervalo?
Eles pertencem ao mesmo intervalo exatamente quando
nums[i+1] == nums[i] + 1. Todos os outros pares de vizinhos marcam o fim de um intervalo e o início do próximo.Lembre-se de onde o intervalo atual começou. Avance enquanto o próximo valor for uma unidade maior que o atual; quando a sequência for interrompida ou o array terminar, escreva o intervalo do início até o valor atual e comece o próximo intervalo no valor seguinte.
Solução
Como os valores estão ordenados e são distintos, um intervalo de inteiros consecutivos é sempre uma sequência de elementos vizinhos no array, e um intervalo termina exatamente onde dois elementos vizinhos diferem em mais de 1. Dividir o array em cada uma dessas lacunas resulta no menor número de intervalos, pois nenhum intervalo pode atravessar uma lacuna. O que resta é apenas manter os registros com cuidado: o início de cada sequência, o último elemento e o formato do texto.
Verifique os dois vizinhos de cada valor
Intuição
Analise um valor de cada vez e faça duas perguntas. Um intervalo começa aqui? Sim, quando este é o primeiro valor ou o valor anterior não é um a menos. Um intervalo termina aqui? Sim, quando este é o último valor ou o valor seguinte não é um a mais.
Em [0, 1, 2, 5, 6, 9], um intervalo começa em 0, 5 e 9, e termina em 2, 6 e 9. Lembre-se do valor em que o intervalo atual começou. Quando um intervalo termina em nums[i], escreva "start->nums[i]", ou apenas "start" quando o intervalo começou e terminou no mesmo valor, como acontece com 9.
Cada valor é visitado uma vez e verifica dois vizinhos, então o tempo é O(n). Além da saída, você mantém um único início guardado, então o espaço extra é O(1).
Algoritmo
- Defina
start = nums[0]. - Para cada índice
i: sei > 0enums[i] != nums[i-1] + 1, definastart = nums[i]. - Se
ifor o último índice ounums[i+1] != nums[i] + 1, o intervalo termina aqui. - Adicione
"start"quandostart == nums[i]; caso contrário,"start->nums[i]". - Retorne a lista após o último índice.
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 rangesDois ponteiros em cada sequência
Intuição
Trate cada intervalo como um bloco do array e encontre suas duas extremidades. O ponteiro i fica no primeiro valor de um intervalo. O ponteiro j começa em i e avança para a direita enquanto o próximo valor for exatamente um a mais, parando no último valor do intervalo.
Para [-3, -1, 0, 1, 4, 7, 8]: i em -3 não pode avançar, porque -1 não é -2, então o intervalo é "-3". Em seguida, i salta para -1, e j avança sobre 0 e 1 e para antes de 4: "-1->1". Depois, "4" e "7->8". Após cada intervalo, i avança para j+1, o primeiro valor do próximo intervalo.
Os intervalos são os menores possíveis em quantidade: dois valores separados por uma lacuna nunca podem pertencer ao mesmo intervalo, e o método só divide nas lacunas. Ambos os ponteiros só avançam, então o loop interno executa n vezes no total em todos os intervalos, mantendo o tempo em O(n) e o espaço extra em O(1).
Algoritmo
- Defina
i = 0. - Defina
j = ie movajpara a direita enquantoj+1 < nenums[j+1] == nums[j] + 1. - Acrescente
"nums[i]"quandoi == j; caso contrário,"nums[i]->nums[j]". - Defina
i = j + 1e repita até queiultrapasse o fim. - Retorne a 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
Armadilhas e casos extremos
A lógica cabe em poucas linhas; os erros estão nos detalhes.
- Esquecer o último intervalo. Um laço que escreve um intervalo apenas quando encontra uma lacuna nunca escreve o último, então
[0, 1, 2, 5, 6, 9]perde seu"9". Feche um intervalo também no último índice. - Escrever
"a->a"para um único valor. Um intervalo de um único valor é escrito como"a". - Exibir valores grandes em notação científica. R transforma um número double como
1000000000em1e+09; converta os valores para inteiros antes de juntá-los.
Perguntas frequentes4
Qual é a complexidade de tempo de Summary Ranges?
O(n). Cada valor é visitado uma vez, e cada intervalo é escrito uma vez. Além da lista de saída, o espaço extra é O(1): o início do intervalo atual e um ou dois índices.
Por que cortar em cada lacuna resulta no menor número de intervalos?
Um intervalo contém números inteiros consecutivos, portanto não pode conter dois valores com um número ausente entre eles. Portanto, cada lacuna no array ordenado deve separar dois intervalos e, com g lacunas, você precisa de pelo menos g+1 intervalos. Dividir apenas nas lacunas resulta em exatamente g+1.
Como lidar com um intervalo com apenas um número?
Verifique se o intervalo começa e termina com o mesmo valor. Se começar e terminar com o mesmo valor, escreva apenas esse valor, como "9". Caso contrário, escreva o início, a seta e o fim, como "5->6". Com dois ponteiros, o teste é i == j.
O Summary Ranges precisa que a entrada esteja ordenada?
Sim. O método compara apenas os vizinhos, então depende de os números inteiros consecutivos estarem lado a lado. Para uma entrada não ordenada, ordene-a primeiro, o que torna a tarefa toda O(n log n), ou coloque os valores em um conjunto hash e amplie cada intervalo a partir do menor valor, como no problema da sequência consecutiva mais longa.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def summaryRanges(nums):
# Escreva o código aquiCaso 1
Caso 2
Entrada
nums = [0, 1, 2, 5, 6, 9]
Esperado
["0->2", "5->6", "9"]