Missing Number
Você recebe uma lista nums com n números inteiros distintos, cada um entre 0 e n. O intervalo de 0 a n contém n+1 números, então exatamente um deles não está na lista. Retorne esse número ausente.
Função
- numsinteger-array
- n inteiros distintos do intervalo de 0 a n, em qualquer ordem
- Retornainteger
- o único número de 0 a n que não está em nums
Restrições
n == nums.length1 ≤ n ≤ 1040 ≤ nums[i] ≤ n- Todos os valores em
numssão distintos.
Exemplos
- Entrada
- nums = [4, 2, 0, 1]
- Saída
- 3
- Explicação
- A lista tem 4 valores, então o intervalo vai de 0 a 4. Ela contém 0, 1, 2 e 4, e 3 é o único número sem correspondência.
- Entrada
- nums = [1]
- Saída
- 0
- Explicação
- Com um valor, o intervalo é 0 e 1. A lista contém 1, então 0 está faltando.
- Entrada
- nums = [0, 1, 2]
- Saída
- 3
- Explicação
- Todos os números abaixo de 3 estão presentes, então o que falta é o próprio 3, o limite superior do intervalo. Ele não é um índice da lista, por isso o limite superior exige cuidado.
+13 testes ocultos ao enviar
Para ir além
Se a lista viesse ordenada, você conseguiria encontrar o número ausente em O(log n) usando busca binária?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Você sabe exatamente quais números a lista deve conter: todos os inteiros de
0an. Existe um número que você possa calcular para esse intervalo completo e comparar com o mesmo número calculado para a lista?Os números inteiros de
0ansomamn(n+1)/2, e a soma da lista é exatamente o valor ausente a menos. O XOR funciona da mesma forma sem nenhum risco de estouro, porque um valor aplicado ao XOR de si mesmo resulta em0.Percorra a lista uma vez mantendo um XOR acumulado. Comece com
ne, em cada índicei, faça XOR comienums[i]. Cada número que aparece duas vezes se cancela, e o que está faltando permanece.
Solução
Você sabe exatamente o que a lista deve conter: todos os números inteiros de 0 a n. Procurar cada um desses números um por um funciona, mas repete uma varredura completa para cada número. Em vez disso, resuma o intervalo completo e a lista em um único valor cada, a soma ou o XOR, e a diferença entre os dois é o número que está faltando. Isso exige uma única passagem e nenhuma memória extra.
Verifique cada candidato
Correta, mas não termina nos maiores testes
Intuição
A resposta é um dos n+1 números de 0 a n. Considere-os em ordem e percorra a lista procurando cada um. O primeiro candidato que não corresponder a nenhum valor é o número ausente.
Isso está correto porque cada número do intervalo está na lista ou é a resposta, e a lista não contém duplicatas; portanto, exatamente um candidato não será encontrado na busca.
Isso é lento porque cada candidato exige percorrer até n valores. Quando a lacuna fica perto do fim, quase todos os candidatos são procurados: com n = 10^4 e a lacuna perto do final, são cerca de 5 × 10^7 comparações. Dobrar o tamanho da lista quadruplica o trabalho.
Algoritmo
- Percorra
candidatede0atén, inclusive. - Procure em
numsum valor igual acandidate. - Se a busca encontrar esse valor, passe para o próximo candidato.
- Se a busca terminar sem encontrar uma correspondência, retorne
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 -1Subtraia a soma da soma esperada
Intuição
Se nada estivesse faltando, a lista conteria todos os números de 0 a n, e a soma deles seria n(n+1)/2. A lista real é esse conjunto completo com um número removido, então sua soma fica exatamente esse número abaixo.
Para [4, 2, 0, 1], n é 4 e a soma do intervalo completo é 4 × 5 / 2 = 10. A soma da lista é 7, e 10 menos 7 resulta em 3.
Uma única passagem soma os valores da lista, então o tempo é O(n), e você mantém um total acumulado. Aqui, a soma completa é no máximo cerca de 5 × 10^7, o que cabe em um inteiro de 32 bits. Para valores muito maiores de n, a fórmula estoura um int de 32 bits, então as versões em Java, C, C++, C# e Rust fazem os cálculos em 64 bits.
Algoritmo
- Seja
no comprimento denums. - Calcule a soma total
n(n+1)/2. - Some todos os valores em
nums. - Retorne a soma total menos a soma da lista.
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)XOR os índices com os valores
Intuição
O XOR cancela pares. a ^ a é 0, a ^ 0 é a, e a ordem das operações não importa. Portanto, se você aplicar XOR a um conjunto de números em que tudo aparece duas vezes, exceto um valor, os pares desaparecem e esse valor é o que resta.
Monte esse conjunto com base no problema: os índices de 0 a n, mais os valores em nums. Um número que está na lista aparece uma vez como índice e outra como valor, então se cancela. O número ausente aparece apenas como índice, então permanece. O loop percorre os índices de 0 a n-1, portanto comece o resultado em n para incluir o último.
Para [4, 2, 0, 1]: comece em 4, depois aplique XOR a 0 e 4, 1 e 2, 2 e 0, 3 e 1. Os 4s, 2s, 1s e 0s se cancelam, e sobra 3. Isso é uma única passagem com um valor acumulado e, ao contrário da soma, ele nunca cresce além dos bits que n já usa, então não pode ocorrer overflow.
Algoritmo
- Defina
resultcomon, o comprimento denums. - Para cada índice
i, faça XOR deresultcomie comnums[i]. - Retorne
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
Armadilhas e casos extremos
A maioria das respostas erradas vem dos dois extremos do intervalo.
- Esquecer que o próprio
npode estar ausente. Em[0, 1, 2], a resposta é 3, que não é um índice da lista. A versão com XOR precisa começar emn, e uma varredura ordenada que procura o primeironums[i] != iprecisa retornarnquando todas as posições corresponderem. - Usar o tamanho errado do intervalo. Os números vão de
0an, ou seja, sãon+1números, então a soma completa én(n+1)/2, não(n-1)n/2. - Supor que
0está sempre presente. Em[1], a resposta é 0, e o código que começa a busca em 1 não o encontra. - Estouro na versão da soma. Em aritmética de 32 bits, o produto
n(n+1)estoura quandonpassa de cerca de 46.000, antes que a divisão por 2 possa ajudar, en(n+1)/2em si deixa de caber perto de 65.000. Use aritmética de 64 bits ou XOR.
Perguntas frequentes4
Qual é a complexidade de tempo de Missing Number?
As soluções com soma e XOR são executadas em O(n) de tempo e usam O(1) de espaço extra, pois leem cada valor uma vez e mantêm um número. Procurar na lista por cada candidato leva O(n²). Ordenar primeiro e procurar a lacuna leva O(n log n).
Por que o XOR encontra o número que está faltando?
Fazer XOR de um número com ele mesmo resulta em 0; fazer XOR com 0 não altera nada, e a ordem não importa. Quando você faz XOR de todos os índices de 0 a n junto com todos os valores, cada número que está na lista aparece duas vezes e se cancela. O número que falta aparece apenas uma vez, como índice, então ele é o resultado.
Você deve usar a fórmula da soma ou XOR?
Ambos fazem uma única passagem e usam memória constante. A soma é mais fácil de explicar, mas, em aritmética de 32 bits, o produto n(n+1) sofre overflow quando n passa de aproximadamente 46.000, então você precisa de aritmética de 64 bits. XOR nunca sofre overflow. Em Python, Ruby e outras linguagens com inteiros ilimitados, essa diferença desaparece.
Você consegue resolver Missing Number com um conjunto hash?
Sim. Coloque todos os valores em um conjunto, depois verifique de 0 a n e retorne o primeiro número que não estiver no conjunto. Isso é executado em tempo O(n), mas usa memória extra O(n), algo que os métodos de soma e XOR evitam.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def missingNumber(nums):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
nums = [4, 2, 0, 1]
Esperado
3