Resumir valores en rangos
La misión
Problema
Recibes una lista ordenada de enteros distintos. Descríbela como la lista más corta posible de rachas de enteros consecutivos, en orden. Escribe una racha como "a->b" cuando cubre más de un valor, y solo como "a" cuando contiene un único valor.
Ejemplos
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é: los valores negativos siguen la misma regla
Input: nums = []
Output: []
Por qué: caso límite: sin valores no hay rachas
Pistas
0 / 3
Como la lista está ordenada y no tiene repetidos, una racha solo puede cortarse entre dos entradas vecinas.
Una racha continúa exactamente mientras cada valor siguiente sea uno más que el anterior. Todo lo demás es llevar la cuenta de dónde empezó la racha actual.
Guarda el índice donde empieza la racha actual. Extiende un índice de fin mientras el siguiente valor sea exactamente uno mayor. Luego escribe la racha, como un solo valor o como inicio, flecha y fin, y empieza la siguiente racha justo después.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- the list is sorted ascending
- the values are distinct integers
Solución
Una entrada ordenada y sin repetidos significa que una racha se corta justo donde dos vecinos difieren en más de uno, así que una sola pasada de izquierda a derecha encuentra todos los límites. El bucle externo marca dónde empieza una racha, el bucle interno estira su fin mientras los valores sigan siendo consecutivos, y luego el par de índices se escribe en el formato que corresponda de los dos. En total, el bucle interno visita cada índice una sola vez, así que el tiempo es O(n) y el espacio es O(1) además de la salida.
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([])) # -> []¿Lo que te frena es la idea y no el código? Intervalos: fundamentos y ordenamiento lo explica.