Summary Ranges
Obtienes un arreglo ordenado nums de enteros distintos. Divídelo en la menor cantidad posible de rangos de enteros consecutivos, de modo que cada valor pertenezca exactamente a un rango. Escribe un rango a..b como el texto "a->b", o como "a" cuando contiene un solo valor. Devuelve los rangos en orden creciente.
Función
- numsinteger-array
- el arreglo ordenado de enteros distintos
- Devuelvestring-array
- los rangos como texto, de los valores más pequeños a los más grandes
Restricciones
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsestá ordenado en orden creciente y no tiene duplicados.
Ejemplos
- Entrada
- nums = [0, 1, 2, 5, 6, 9]
- Salida
- ["0->2", "5->6", "9"]
- Explicación
0, 1, 2van seguidos, así que forman"0->2". El salto de 2 a 5 inicia un nuevo intervalo,"5->6", y 9 queda solo como"9".
- Entrada
- nums = [-3, -1, 0, 1, 4, 7, 8]
- Salida
- ["-3", "-1->1", "4", "7->8"]
- Explicación
- A -3 le falta un vecino (falta -2),
-1, 0, 1forman una secuencia, 4 queda aislado y7, 8cierran la lista. Los valores negativos funcionan igual: después de -1 viene -1 + 1 = 0.
+16 pruebas ocultas al enviar
Para ir más allá
Supón que nums podría contener duplicados, como [1, 2, 2, 3]. ¿Qué cambiarías para que siga imprimiendo "1->3"?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
El arreglo está ordenado. ¿Cuándo pertenecen dos valores vecinos al mismo rango?
Pertenecen al mismo rango exactamente cuando
nums[i+1] == nums[i] + 1. Cualquier otro par de elementos vecinos marca el final de un rango y el comienzo del siguiente.Recuerda dónde empezó el rango actual. Avanza mientras el siguiente valor sea uno más que el actual; cuando se interrumpa la secuencia o termine el array, escribe el rango desde su inicio hasta el valor actual y comienza el siguiente rango en el valor siguiente.
Solución
Como los valores están ordenados y son distintos, un intervalo de enteros consecutivos siempre es una secuencia de elementos vecinos en el array, y un intervalo termina exactamente donde dos elementos vecinos difieren en más de 1. Dividir el array en cada uno de esos huecos da el menor número de intervalos, ya que ningún intervalo puede cruzar un hueco. Lo que queda es llevar un registro cuidadoso: el inicio de cada secuencia, el último elemento y el formato del texto.
Comprueba ambos vecinos de cada valor
Intuición
Observa un valor a la vez y hazte dos preguntas. ¿Se abre un rango aquí? Sí, cuando este es el primer valor o el valor anterior no es uno menos. ¿Se cierra un rango aquí? Sí, cuando este es el último valor o el valor siguiente no es uno más.
En [0, 1, 2, 5, 6, 9], se abre un rango en 0, 5 y 9, y se cierra en 2, 6 y 9. Recuerda el valor donde se abrió el rango actual. Cuando un rango se cierra en nums[i], escribe "start->nums[i]", o solo "start" cuando el rango se abrió y se cerró en el mismo valor, como ocurre con 9.
Se visita cada valor una vez y se observan dos vecinos, así que el tiempo es O(n). Aparte de la salida, guardas un inicio en la memoria, así que el espacio adicional es O(1).
Algoritmo
- Establece
start = nums[0]. - Para cada índice
i: sii > 0ynums[i] != nums[i-1] + 1, establecestart = nums[i]. - Si
ies el último índice onums[i+1] != nums[i] + 1, el rango se cierra aquí. - Añade
"start"cuandostart == nums[i]; de lo contrario, añade"start->nums[i]". - Devuelve la lista después del ú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 rangesDos punteros sobre cada secuencia
Intuición
Trata cada rango como un bloque del arreglo y encuentra sus dos extremos. El puntero i está en el primer valor de un rango. El puntero j comienza en i y se mueve hacia la derecha mientras el siguiente valor sea exactamente uno más, así que se detiene en el último valor del rango.
Para [-3, -1, 0, 1, 4, 7, 8]: i en -3 no puede avanzar, porque -1 no es -2, así que el rango es "-3". Después i salta a -1, y j avanza sobre 0 y 1 y se detiene antes de 4: "-1->1". Después, "4" y "7->8". Después de cada rango, i avanza a j+1, el primer valor del siguiente.
Los rangos son los menos posibles: dos valores separados por un hueco nunca pueden compartir un rango, y el método solo divide en los huecos. Ambos punteros solo avanzan, así que el bucle interno se ejecuta n veces en total entre todos los rangos, lo que mantiene el tiempo en O(n) y el espacio adicional en O(1).
Algoritmo
- Establece
i = 0. - Establece
j = iy muevejhacia la derecha mientrasj+1 < nynums[j+1] == nums[j] + 1. - Añade
"nums[i]"cuandoi == j; de lo contrario, añade"nums[i]->nums[j]". - Establece
i = j + 1y repite hasta queipase el final. - Devuelve 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
Errores comunes y casos límite
La lógica cabe en unas pocas líneas; los errores están en los casos límite.
- Olvidar el último intervalo. Un bucle que escribe un intervalo solo cuando encuentra una discontinuidad nunca escribe el último, así que
[0, 1, 2, 5, 6, 9]pierde su"9". Cierra también un intervalo en el último índice. - Escribir
"a->a"para un solo valor. Un intervalo de un solo valor se escribe como"a". - Imprimir valores grandes en notación científica. R convierte un número de doble precisión como
1000000000en1e+09; convierte los valores en enteros antes de pegarlos.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Summary Ranges?
O(n). Cada valor se visita una vez y cada rango se escribe una vez. Aparte de la lista de salida, el espacio adicional es O(1): el inicio del rango actual y uno o dos índices.
¿Por qué cortar en cada espacio da la menor cantidad de rangos?
Un intervalo contiene números enteros consecutivos, por lo que no puede contener dos valores con un número ausente entre ellos. Por lo tanto, cada hueco en el arreglo ordenado debe separar dos intervalos y, con g huecos, necesitas al menos g+1 intervalos. Cortar solo en los huecos da exactamente g+1.
¿Cómo manejas un rango que tiene un solo número?
Comprueba si el rango empieza y termina en el mismo valor. Si es así, escribe solo ese valor, como "9". Si no, escribe el inicio, la flecha y el final, como "5->6". Con dos punteros, la comprobación es i == j.
¿Es necesario que la entrada esté ordenada para los rangos resumidos?
Sí. El método solo compara los valores vecinos, por lo que depende de que los enteros consecutivos estén uno al lado del otro. Para una entrada sin ordenar, ordénala primero, lo que hace que toda la tarea sea O(n log n), o coloca los valores en un conjunto hash y amplía cada rango a partir de su valor más pequeño, como en el problema de la secuencia consecutiva más larga.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def summaryRanges(nums):
# Escribe el código aquíCaso 1
Caso 2
Entrada
nums = [0, 1, 2, 5, 6, 9]
Esperado
["0->2", "5->6", "9"]