First Missing Positive

+10

Recibes un array desordenado de enteros nums. Devuelve el entero positivo más pequeño (1 o mayor) que no aparece en nums. El array puede contener números negativos, ceros, valores repetidos y valores mucho mayores que su longitud.

Función

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: los enteros sin ordenar, que pueden repetirse y ser negativos, cero o muy grandes
Devuelveinteger: el entero positivo más pequeño que falta en nums

Restricciones

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Los valores no están en ningún orden en particular y pueden repetirse.

Ejemplos

Entrada: nums = [5, -2, 1, 3, 2, 9]
Salida: 4
Explicación: 1, 2 y 3 están todos en el array y 4 no está, así que la respuesta es 4. El 5 y el 9 no importan una vez que falta un valor menor.

Para ir más allá

¿Puedes encontrar la respuesta en tiempo O(n) usando solo O(1) de memoria adicional?

Pistas

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

0 de 3 abiertas

Solución

La ordenación requiere un tiempo O(n log n) y un conjunto hash, O(n) de memoria adicional. Un límite supera a ambos: n valores cubren como máximo n de los números del 1 al n+1, así que la respuesta es como máximo n+1. Solo importan los valores del 1 al n, y el arreglo tiene n posiciones para registrarlos, así que la memoria adicional se reduce a O(1).

Prueba cada candidato con un escaneo completo

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

Intuición

Prueba los candidatos 1, 2, 3, ... en orden. Para cada uno, recorre todo el arreglo y devuelve el primer candidato que el recorrido no encuentre. Por la cota, nunca pruebas más allá de n+1.

Cuando el arreglo contiene los valores del 1 al n, en promedio cada candidato se encuentra a mitad del recorrido, así que n = 10^4 cuesta aproximadamente n²/2 = 5 × 10^7 comparaciones.

Algoritmo

Establece candidate en 1.
Busca en nums un elemento igual a candidate y detente en el primero.
Si ningún elemento coincide, devuelve candidate.
De lo contrario, suma 1 a candidate y vuelve a buscar. Nunca pasas de n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Marca los valores de 1 a n en un arreglo de indicadores

Intuición

Como la respuesta es como máximo n+1, omite cualquier valor menor que 1 o mayor que n. Un arreglo booleano present de longitud n+1 registra el resto, así que nunca se almacena un valor como 10^9. Devuelve el primer v de 1 a n cuyo indicador es false, o n+1 si todos los indicadores están activados.

En el primer ejemplo, n = 6: se activan los indicadores de 1, 2, 3 y 5; se omiten -2 y 9, y el primer indicador desactivado es el de 4. Dos recorridos lineales dan un tiempo O(n), y los indicadores cuestan O(n) de memoria.

Algoritmo

Crea present, con n+1 indicadores establecidos en false.
Para cada valor v en nums con 1 ≤ v ≤ n, establece present[v] en true.
Devuelve el primer v de 1 a n cuyo indicador sea false.
Si no hay ninguno, devuelve n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Coloca cada valor en su propia ranura

Intuición

El valor v pertenece al índice v-1. Con cada valor del 1 al n en su lugar, el primer índice i que no contiene i+1 indica la respuesta.

En cada índice, intercambia el valor a su lugar mientras esté entre 1 y n y su lugar no lo contenga ya. Puede que también haya que mover el valor que vuelve. Comprobar el lugar, no i, evita los duplicados: en [1, 1], el segundo 1 encuentra un 1 en el índice 0 y se queda.

En el primer ejemplo, el índice 0 envía el 5 a su lugar y luego el 2 que vuelve; más tarde, el 1 y el 3 van a su lugar, dejando [1, 2, 3, -2, 5, 9]: el índice 3 es la primera posición incorrecta, así que la respuesta es 4.

Cada intercambio coloca definitivamente un valor en su lugar, así que los bucles internos realizan como máximo n intercambios en total: tiempo O(n) y memoria O(1), excepto en R, que copia el vector que modifica.

Algoritmo

Para cada índice i de 0 a n-1:
Mientras 1 ≤ nums[i] ≤ n y nums[nums[i]-1] ≠ nums[i], intercambia nums[i] con nums[nums[i]-1].
Después de la pasada de colocación, encuentra el primer índice i donde nums[i] ≠ i+1 y devuelve i+1.
Si cada posición contiene su propio valor, devuelve n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Errores comunes y casos límite

Detener los intercambios cuando nums[i] == i+1 en lugar de cuando la posición correcta ya contiene el valor. Con [1, 1], los dos 1 se intercambian para siempre.
Intercambiar con if en lugar de while. En el primer ejemplo, el 2 que vuelve del índice 4 nunca llega al índice 1, y devuelves 2 en lugar de 4.
Escribir nums[i] = nums[nums[i]-1] y luego volver a usar el índice nums[i], lo que lee el índice de destino después de que haya cambiado. Guarda primero el índice de destino.
Omitir la comprobación de rango, lo que envía 0, -2 o 10^9 a un índice fuera del arreglo.
Devolver n cuando todas las posiciones están bien. Para [4, 2, 1, 3], la respuesta es 5.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de First Missing Positive?

La solución de colocación se ejecuta en tiempo O(n) y usa O(1) espacio adicional. El bucle while está dentro de un bucle for, pero cada intercambio coloca un valor en su índice final, así que la ejecución completa realiza como máximo n intercambios. La versión con un arreglo de indicadores se ejecuta en tiempo O(n) y usa O(n) memoria, y buscar cada candidato requiere O(n²).

¿Por qué la respuesta nunca es mayor que n+1?

Los números del 1 al n+1 son n+1 valores diferentes, y un arreglo de longitud n contiene como máximo n valores diferentes, así que falta uno de ellos. La respuesta es n+1 exactamente cuando el arreglo contiene todos los valores del 1 al n.

¿La solución in situ modifica el arreglo de entrada?

Sí, reorganiza los valores. Si quien llama necesita el orden original, primero copia el arreglo, lo que vuelve a elevar el uso de memoria a O(n). Otro método in situ reemplaza cada valor fuera del rango de 1 a n por n+1 y luego marca que v está presente haciendo que nums[v-1] sea negativo; también modifica el arreglo.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [5, -2, 1, 3, 2, 9]

Salida Esperada

First Missing Positive

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada candidato con un escaneo completo

Marca los valores de 1 a n en un arreglo de indicadores

Coloca cada valor en su propia ranura

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares