Missing Number

Q: ¿Cuál es la complejidad temporal de Missing Number?

Las soluciones de suma y XOR se ejecutan en tiempo O(n) con espacio adicional O(1) , ya que leen cada valor una vez y mantienen un número. Buscar en la lista cada candidato requiere O(n²) . Ordenar primero y buscar el intervalo requiere O(n log n) .

FácilManipulación de bits Matemáticas y simulación

+10

Recibes una lista nums de n enteros distintos, cada uno entre 0 y n. El rango de 0 a n contiene n+1 números, así que exactamente uno de ellos no está en la lista. Devuelve ese número faltante.

Función

missingNumber(nums: integer-array) → integer

numsinteger-array: n enteros distintos del rango de 0 a n, en cualquier orden
Devuelveinteger: el único número de 0 a n que no está en nums

Restricciones

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Todos los valores de nums son distintos.

Ejemplos

Entrada: nums = [4, 2, 0, 1]
Salida: 3
Explicación: La lista tiene 4 valores, así que el rango va de 0 a 4. Contiene 0, 1, 2 y 4, y 3 es el único número sin coincidencia.

+13 pruebas ocultas al enviar

Para ir más allá

Si la lista estuviera ordenada, ¿podrías encontrar el número que falta en O(log n) tiempo usando búsqueda binaria?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Sabes exactamente qué debe contener la lista: todos los enteros desde 0 hasta n. Buscar cada uno de esos números de uno en uno funciona, pero repite un recorrido completo por cada número. En su lugar, condensa el rango completo y la lista en un único valor resumen cada uno, la suma o el XOR, y la diferencia entre ambos es el número que falta. Eso requiere una sola pasada y no usa memoria adicional.

Comprueba cada candidato

Correcto, pero no termina con las pruebas más grandes

Intuición

La respuesta es uno de los n+1 números de 0 a n. Tómalos en orden y recorre la lista buscando cada uno. El primer candidato que no coincide con ningún valor es el número que falta.

Esto es correcto porque cada número del intervalo está en la lista o es la respuesta, y la lista no tiene duplicados, así que exactamente un candidato no aparece en la búsqueda.

Es lento porque cada candidato requiere recorrer hasta n valores. Cuando el hueco está cerca del final, se busca casi cada candidato: con n = 10^4 y el hueco cerca del final, eso supone alrededor de 5 × 10^7 comparaciones. Duplicar la lista hace que el trabajo sea cuatro veces mayor.

Algoritmo

Recorre candidate desde 0 hasta n, inclusive.
Busca en nums un valor igual a candidate.
Si la búsqueda lo encuentra, pasa al siguiente candidato.
Si la búsqueda termina sin encontrar coincidencias, devuelve candidate.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

Resta la suma de la suma esperada

Intuición

Si no faltara nada, la lista contendría todos los números desde 0 hasta n, y su suma sería n(n+1)/2. La lista real es ese conjunto completo al que se le ha quitado un número, así que su suma es exactamente ese número menor.

Para [4, 2, 0, 1], n es 4 y la suma del rango completo es 4 × 5 / 2 = 10. La lista suma 7, y 10 menos 7 da 3.

Un solo recorrido suma los elementos de la lista, así que el tiempo es O(n) y mantienes un único total acumulado. Aquí la suma completa es como máximo aproximadamente 5 × 10^7, lo que cabe en un entero de 32 bits. Para valores de n mucho mayores, la fórmula desborda un entero de 32 bits, así que las versiones de Java, C, C++, C# y Rust realizan las operaciones aritméticas en 64 bits.

Algoritmo

Sea n la longitud de nums.
Calcula la suma completa n(n+1)/2.
Suma todos los valores de nums.
Devuelve la suma completa menos la suma de la lista.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Aplica XOR a los índices con los valores

Intuición

XOR cancela los pares. a ^ a es 0, a ^ 0 es a, y el orden de las operaciones no importa. Así que, si aplicas XOR a un conjunto de números en el que todos aparecen dos veces excepto un valor, los pares desaparecen y ese valor es lo que queda.

Construye ese conjunto a partir del problema: los índices del 0 al n más los valores de nums. Un número que está en la lista aparece una vez como índice y otra como valor, así que se cancela. El número que falta aparece solo como índice, así que permanece. El bucle recorre los índices del 0 al n-1, así que empieza el resultado en n para incluir el último.

Para [4, 2, 0, 1]: empieza en 4; después aplica XOR a 0 y 4, 1 y 2, 2 y 0, 3 y 1. Los 4, los 2, los 1 y los 0 se cancelan, y queda 3. Esto requiere una sola pasada con un único valor acumulado y, a diferencia de la suma, nunca crece más allá de los bits que n ya usa, así que no puede desbordarse.

Algoritmo

Establece result en n, la longitud de nums.
Para cada índice i, aplica XOR a result con i y con nums[i].
Devuelve result.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a los dos extremos del rango.

Olvidar que n también puede faltar. En [0, 1, 2], la respuesta es 3, que no es un índice de la lista. La versión con XOR debe empezar en n, y un recorrido ordenado que busque el primer nums[i] != i debe devolver n cuando todas las posiciones coincidan.
Usar el tamaño de rango incorrecto. Los números van de 0 a n, es decir, son n+1 números, así que la suma completa es n(n+1)/2, no (n-1)n/2.
Suponer que 0 siempre está presente. En [1], la respuesta es 0, y el código que inicia la búsqueda en 1 no lo encuentra.
Desbordamiento en la versión de la suma. En aritmética de 32 bits, el producto n(n+1) se desborda cuando n supera aproximadamente 46 000, antes de que la división por 2 pueda ayudar, y n(n+1)/2 deja de caber cerca de 65 000. Usa aritmética de 64 bits o XOR.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Missing Number?

Las soluciones de suma y XOR se ejecutan en tiempo O(n) con espacio adicional O(1), ya que leen cada valor una vez y mantienen un número. Buscar en la lista cada candidato requiere O(n²). Ordenar primero y buscar el intervalo requiere O(n log n).

¿Por qué XOR encuentra el número que falta?

Aplicar XOR a un número consigo mismo da 0; aplicar XOR con 0 no cambia nada, y el orden no importa. Cuando aplicas XOR a todos los índices del 0 al n junto con todos los valores, cada número que está en la lista aparece dos veces y se cancela. El número que falta aparece solo una vez, como índice, así que es el resultado.

¿Deberías usar la fórmula de la suma o XOR?

Ambos requieren una pasada y memoria constante. La suma es más fácil de explicar, pero con aritmética de 32 bits el producto n(n+1) se desborda cuando n supera aproximadamente 46 000, así que necesitas aritmética de 64 bits. XOR nunca se desborda. En Python, Ruby y otros lenguajes con enteros ilimitados, la diferencia desaparece.

¿Puedes resolver Missing Number con un conjunto hash?

Sí. Coloca todos los valores en un conjunto, después comprueba desde 0 hasta n y devuelve el primer número que falte en el conjunto. Esto se ejecuta en tiempo O(n), pero usa O(n) de memoria adicional, algo que los métodos de suma y XOR evitan.

Python

def missingNumber(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [4, 2, 0, 1]

Esperado

Missing Number

Función

Restricciones

Ejemplos

Pistas

Solución

Comprueba cada candidato

Resta la suma de la suma esperada

Aplica XOR a los índices con los valores

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares