Longest Consecutive Sequence
Recibes un arreglo de enteros nums sin ningún orden particular. Una secuencia consecutiva es un grupo de valores x, x+1, x+2 y así sucesivamente, cada uno de los cuales aparece en algún lugar de nums. Devuelve la longitud de la secuencia consecutiva más larga. Un valor que aparece más de una vez cuenta una sola vez.
Función
- numsinteger-array
- los números enteros, en cualquier orden, se permiten repeticiones
- Devuelveinteger
- la longitud de la secuencia más larga de valores consecutivos presentes en nums
Restricciones
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- Los valores pueden repetirse. Las posiciones en el arreglo no importan, solo qué valores están presentes.
Ejemplos
- Entrada
- nums = [40, 4, 39, 1, 3, 2, 41]
- Salida
- 4
- Explicación
1,2,3y4están todos presentes, una secuencia de 4, aunque estén dispersos por el arreglo. La otra secuencia, de39a41, tiene solo 3 valores.
- Entrada
- nums = [7, 3, 7, 5, 6, 5]
- Salida
- 3
- Explicación
5,6y7forman una secuencia de 3. El segundo7y el segundo5no añaden nada, y3no puede unirse porque falta4.
- Entrada
- nums = [10, 30, 20]
- Salida
- 1
- Explicación
- Ningún par de valores difiere en 1, así que cada secuencia contiene un solo valor y la respuesta es 1.
Para ir más allá
Supón que los valores llegan de uno en uno y que, después de cada uno, debes indicar la secuencia más larga hasta el momento. ¿Puedes mantener la respuesta actualizada en O(1) tiempo promedio por valor?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Prueba cada valor como primer número de una secuencia y cuenta hacia arriba. ¿Qué pregunta haces una y otra vez, y cuánto cuesta cada respuesta cuando lo buscas en el array?
La pregunta es «¿
x+1está en el array?». Un conjunto hash responde en tiempo constante en promedio y también elimina los repetidos.Empieza a contar solo desde un valor
xcuyox-1no esté en el conjunto. Desde ahí, avanza ax+1,x+2y así sucesivamente mientras el conjunto los contenga, y conserva el recorrido más largo. Así, cada valor se recorre una sola vez.
Solución
Los valores de una secuencia pueden estar en cualquier parte del arreglo. Ordenarlos los organiza en O(n log n). Un conjunto hash responde «¿está aquí x+1?» en O(1), y si solo cuentas a partir de los valores cuyo x-1 no está, se recorre cada valor una vez: O(n) en total.
Cuenta hacia arriba desde cada valor buscando en el array
Correcto, pero no termina con las pruebas más grandes
Intuición
Considera cada valor como un posible inicio de una secuencia. Desde x, busca en el arreglo x+1, después x+2, hasta que falte un valor, y conserva el conteo más largo. Toda secuencia tiene un valor mínimo en nums, y el bucle recorre toda la secuencia desde ese valor.
Cada búsqueda lee hasta n valores, y una secuencia larga se recorre de nuevo desde cada uno de sus elementos. Para 10^4 valores que forman una sola secuencia desordenada, los recorridos toman alrededor de n²/2 = 5 × 10^7 pasos, cada uno examinando en promedio la mitad del arreglo: alrededor de 2.5 × 10^11 comparaciones.
Algoritmo
- Establece
besten 0. - Para cada valor
startennums, establececurrentenstartylengthen 1. - Mientras un recorrido de
numsencuentrecurrent+1, suma 1 acurrenty alength. - Guarda
lengthenbestsi es mayor. - Devuelve
best.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return bestOrdenar y luego contar las secuencias
Intuición
La ordenación coloca los valores de cada secuencia uno junto a otro: [40, 4, 39, 1, 3, 2, 41] se convierte en [1, 2, 3, 4, 39, 40, 41], y las secuencias se leen de izquierda a derecha.
Recorre los valores ordenados y lleva la cuenta de la longitud de la secuencia actual. Un valor que sea uno más que el anterior la extiende. Un valor repetido no extiende la secuencia ni la termina, así que sáltatelo. Cualquier otro valor inicia una nueva secuencia de longitud 1.
La ordenación cuesta O(n log n) y el recorrido, O(n). Ordenar en el mismo lugar no requiere ninguna matriz adicional; los lenguajes que ordenan una copia usan O(n) de memoria.
Algoritmo
- Ordena
numsen orden ascendente. - Establece
bestyrunen 1, ya que el array nunca está vacío. - Para cada índice
ia partir de 1, omitenums[i]si es igual anums[i-1]. - Si
nums[i]esnums[i-1]+1, suma 1 arun; de lo contrario, establecerunen 1. Guardarunenbestsi es mayor. - Devuelve
best.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestConjunto hash, contando solo desde el inicio de cada ejecución
Intuición
Con cada valor de un conjunto hash, comprobar la pertenencia cuesta O(1) en promedio y los valores repetidos se agrupan en una sola entrada.
Recorrer desde cada valor seguiría repitiendo trabajo: en la secuencia 1, 2, 3, 4, darías 3 pasos desde 1, 2 desde 2 y 1 desde 3. Así que recorre solo desde el primer valor de una secuencia, que es exactamente un valor x para el que falta x-1. En el ejemplo 1, solo 1 y 39 cumplen esta condición, formando secuencias de 4 y 3.
Cada valor pertenece a una secuencia y solo el recorrido de esa secuencia pasa por él, así que todos los recorridos juntos dan como máximo n pasos. Con una comprobación por valor, el total es O(n) de tiempo y O(n) de memoria para el conjunto.
Algoritmo
- Introduce cada valor de
numsen un conjunto hashvaluesy establecebesten 0. - Para cada valor
xdel conjunto, sáltatelo six-1está en el conjunto: no es el primer valor de su secuencia. - De lo contrario, establece
endenxy súmale 1 mientrasend+1esté en el conjunto. - Guarda
end-x+1enbestsi es mayor. - Devuelve
best.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
Errores comunes y casos límite
- Tratar un valor repetido como un hueco o como un paso después de ordenar. En
[1, 2, 2, 3], reiniciar la secuencia en el segundo2da 2, y contarlo como un paso da 4. La respuesta es 3. - Empezar
besten 0 en el recorrido ordenado y actualizarlo solo dentro del bucle. Un arreglo con un solo valor devuelve 0 en lugar de 1. - Recorrer cada valor del conjunto en vez de empezar solo desde el inicio de cada secuencia. Recorrer una secuencia de
10^4valores cuesta entonces5 × 10^7pasos. - Iterar sobre
numsen vez de sobre el conjunto. Si el primer valor de una secuencia de 2,500 aparece 2,000 veces, se recorre la secuencia 2,000 veces. - Indexar un arreglo por valor. Los valores llegan hasta
±10^9, así que se necesitan2 × 10^9entradas.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de la secuencia consecutiva más larga?
La solución con un conjunto hash se ejecuta en tiempo O(n) en promedio y usa O(n) de memoria adicional. Ordenar y contar las secuencias toma O(n log n). Buscar en el arreglo cada siguiente valor sin un conjunto toma hasta O(n³).
¿Puedes resolver la secuencia consecutiva más larga sin memoria adicional?
Sí, si puedes reordenar la entrada: ordénala en el sitio y cuenta las secuencias en una pasada, omitiendo las repeticiones. Eso usa memoria adicional O(1), pero tarda O(n log n). La solución O(n) necesita el conjunto hash.
¿Puede union-find resolver la secuencia consecutiva más larga?
Sí. Convierte cada valor distinto en un conjunto, une x con x+1 siempre que ambos estén presentes y devuelve el tamaño del conjunto más grande. Se ejecuta en un tiempo cercano a O(n), pero necesita un mapa de valores a índices, enlaces a los padres y tamaños, mientras que el recorrido con un conjunto hash necesita un solo conjunto.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def longestConsecutive(nums):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
nums = [40, 4, 39, 1, 3, 2, 41]
Salida Esperada
4