First Missing Positive

+10

Você recebe um array não ordenado de inteiros nums. Retorne o menor inteiro positivo (1 ou maior) que não aparece em nums. O array pode conter números negativos, zeros, valores repetidos e valores muito maiores que seu comprimento.

Função

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: os números inteiros não ordenados, que podem se repetir e ser negativos, zero ou muito grandes
Retornainteger: o menor número inteiro positivo que está ausente em nums

Restrições

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Os valores não estão em nenhuma ordem específica e podem se repetir.

Exemplos

Entrada: nums = [5, -2, 1, 3, 2, 9]
Saída: 4
Explicação: 1, 2 e 3 estão todos no array e 4 não está, então a resposta é 4. O 5 e o 9 não importam quando um valor menor está faltando.

Para ir além

Você consegue encontrar a resposta em O(n) de tempo usando apenas O(1) de memória extra?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A ordenação leva tempo O(n log n) e um conjunto hash usa O(n) de memória extra. Um limite supera ambos: n valores abrangem no máximo n dos números de 1 a n+1, então a resposta é no máximo n+1. Apenas os valores de 1 a n importam, e o array tem n posições para registrá-los, então a memória extra cai para O(1).

Teste cada candidato com uma varredura completa

Correta, mas não termina nos maiores testes

Intuição

Teste os candidatos 1, 2, 3, ... em ordem. Para cada um, percorra todo o array e retorne o primeiro candidato que a busca não encontrar. Pelo limite, você nunca testa além de n+1.

Quando o array contém valores de 1 a n, cada candidato é encontrado, em média, na metade da busca; portanto, n = 10^4 custa cerca de n²/2 = 5 × 10^7 comparações.

Algoritmo

Defina candidate como 1.
Percorra nums em busca de um elemento igual a candidate, parando no primeiro que encontrar.
Se nenhum elemento corresponder, retorne candidate.
Caso contrário, some 1 a candidate e percorra novamente. Você nunca ultrapassa 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

Marque os valores de 1 a n em um array de flags

Intuição

Como a resposta é no máximo n+1, ignore qualquer valor menor que 1 ou maior que n. Um array booleano present de comprimento n+1 registra os demais, então um valor como 10^9 nunca é armazenado. Retorne o primeiro v de 1 a n cuja flag seja falsa, ou n+1 se todas as flags estiverem definidas.

No primeiro exemplo, n = 6: as flags de 1, 2, 3 e 5 são definidas, -2 e 9 são ignorados, e a primeira flag não definida é 4. Duas passagens lineares levam tempo O(n), e as flags consomem memória O(n).

Algoritmo

Crie present, n+1 sinalizadores definidos como false.
Para cada valor v em nums com 1 ≤ v ≤ n, defina present[v] como true.
Retorne o primeiro v de 1 a n cujo sinalizador seja false.
Se não houver nenhum, retorne 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

Coloque cada valor em seu próprio espaço

Intuição

O valor v pertence ao índice v-1. Com todos os valores de 1 a n em suas posições, o primeiro índice i que não contém i+1 indica a resposta.

Em cada índice, troque o valor para sua posição enquanto ele estiver entre 1 e n e a posição correspondente ainda não o contiver. O valor que volta também pode precisar ser movido. Verificar a posição correspondente, e não i, impede duplicatas: em [1, 1], o segundo 1 encontra um 1 no índice 0 e permanece onde está.

No primeiro exemplo, o índice 0 envia o 5 para sua posição e, em seguida, o 2 que volta; mais adiante, o 1 e o 3 vão para suas posições, deixando [1, 2, 3, -2, 5, 9]: o índice 3 é a primeira posição incorreta, então a resposta é 4.

Cada troca coloca um valor definitivamente em sua posição, então os laços internos fazem no máximo n trocas no total: tempo O(n) e memória O(1), exceto em R, que copia o vetor que modifica.

Algoritmo

Para cada índice i de 0 a n-1:
Enquanto 1 ≤ nums[i] ≤ n e nums[nums[i]-1] ≠ nums[i], troque nums[i] por nums[nums[i]-1].
Após a etapa de posicionamento, encontre o primeiro índice i em que nums[i] ≠ i+1 e retorne i+1.
Se cada posição contiver seu próprio valor, retorne 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

Armadilhas e casos extremos

Interromper as trocas quando nums[i] == i+1 em vez de quando a posição correta já contém o valor. Com [1, 1], os dois valores 1 são trocados para sempre.
Usar if em vez de while para fazer a troca. No primeiro exemplo, o 2 que volta do índice 4 nunca chega ao índice 1, e você retorna 2 em vez de 4.
Escrever nums[i] = nums[nums[i]-1] e depois indexar novamente com nums[i], o que lê o índice da posição correta depois que ele mudou. Salve primeiro o índice da posição correta.
Pular a verificação do intervalo, o que envia 0, -2 ou 10^9 para um índice fora do array.
Retornar n quando todas as posições estão corretas. Para [4, 2, 1, 3], a resposta é 5.

Perguntas frequentes3

Qual é a complexidade de tempo do Primeiro Positivo Ausente?

A solução de posicionamento é executada em O(n) de tempo, com O(1) de espaço extra. O laço while fica dentro de um laço for, mas cada troca coloca um valor em seu índice final, então a execução inteira realiza no máximo n trocas. A versão com array de flags tem complexidade O(n) de tempo e O(n) de memória, e a busca por cada candidato é O(n²).

Por que a resposta nunca é maior que n+1?

Os números de 1 a n+1 são n+1 valores diferentes, e um array de comprimento n contém no máximo n valores diferentes, então um deles está faltando. A resposta é n+1 exatamente quando o array contém todos os valores de 1 a n.

A solução in-place altera o array de entrada?

Sim, ele reorganiza os valores. Se quem chamou a função precisar da ordem original, copie o array primeiro, o que faz a memória extra voltar a ser O(n). Outro método in-place substitui cada valor fora do intervalo de 1 a n por n+1 e, em seguida, marca v como presente tornando nums[v-1] negativo; ele também altera o array.

def firstMissingPositive(nums):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

First Missing Positive

Função

Restrições

Exemplos

Dicas

Solução

Teste cada candidato com uma varredura completa

Marque os valores de 1 a n em um array de flags

Coloque cada valor em seu próprio espaço

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos