Condensar valores em faixas
A missão
Problema
Você recebe uma lista ordenada de inteiros distintos. Descreva-a como a menor lista possível de sequências de inteiros consecutivos, em ordem. Escreva uma sequência como "a->b" quando ela cobre mais de um valor, e apenas como "a" quando ela contém um único valor.
Exemplos
Input: nums = [0, 1, 2, 4, 5, 7]
Output: ["0->2", "4->5", "7"]
Input: nums = [-3, -1, 0]
Output: ["-3", "-1->0"]
Por quê: valores negativos seguem a mesma regra
Input: nums = []
Output: []
Por quê: edge case: sem valores, não há sequências
Dicas
0 / 3
Como a lista está ordenada e não tem repetições, uma sequência só pode se romper entre duas entradas vizinhas.
Uma sequência continua exatamente enquanto cada próximo valor é uma unidade maior que o anterior. O resto é só controlar onde a sequência atual começou.
Guarde o índice onde a sequência atual começa. Avance um índice de fim enquanto o próximo valor for exatamente uma unidade maior. Depois, escreva a sequência, como um valor único ou como início, seta e fim, e comece a próxima logo depois dela.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- the list is sorted ascending
- the values are distinct integers
Solução
Com uma entrada ordenada e sem repetições, uma sequência se rompe exatamente onde dois vizinhos diferem em mais de um, então uma única varredura da esquerda para a direita encontra todas as fronteiras. O loop externo marca onde uma sequência começa, o loop interno estende o seu fim enquanto os valores continuam consecutivos, e o par de índices é então escrito no formato que se aplica dos dois. No total, o loop interno visita cada índice uma vez, então o tempo é O(n) e o espaço é O(1) além da saída.
def condense(nums):
out, i = [], 0
while i < len(nums):
j = i
while j + 1 < len(nums) and nums[j + 1] == nums[j] + 1:
j += 1 # the run is still consecutive
out.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
i = j + 1 # next run starts after this one
return out
print(condense([0, 1, 2, 4, 5, 7])) # -> ['0->2', '4->5', '7']
print(condense([-3, -1, 0])) # -> ['-3', '-1->0']
print(condense([])) # -> []Travou na ideia, e não no código? O básico de intervalos e ordenação explica isso.