Single Number
Você recebe uma lista nums na qual cada valor aparece exatamente duas vezes, exceto um valor que aparece apenas uma vez. Retorne o valor que aparece uma vez.
Função
- numsinteger-array
- uma lista em que cada valor aparece duas vezes, exceto um
- Retornainteger
- o valor que aparece apenas uma vez
Restrições
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Cada valor aparece exatamente duas vezes, exceto um valor que aparece exatamente uma vez.
Exemplos
- Entrada
- nums = [8, 3, 8]
- Saída
- 3
- Explicação
- 8 aparece duas vezes e 3 aparece uma vez, então a resposta é 3.
- Entrada
- nums = [5, -2, 7, 5, 7]
- Saída
- -2
- Explicação
- 5 e 7 aparecem duas vezes cada, e -2 é o único valor que aparece uma vez. Uma resposta negativa é encontrada da mesma forma que uma positiva.
- Entrada
- nums = [42]
- Saída
- 42
- Explicação
- Uma lista com um único valor não tem nenhum par, então esse valor é a resposta.
Para ir além
E se cada valor aparecesse três vezes, exceto um? XOR sozinho não cancela mais os trios. Você ainda consegue encontrar o valor único em O(n) de tempo e O(1) de memória extra?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Se todo par de valores iguais pudesse desaparecer, só restaria a resposta. Existe uma operação que transforma dois números iguais em nada?
XOR faz:
x ^ xé0ex ^ 0éx. Também não depende da ordem, então as duas cópias de um valor não precisam ficar lado a lado para se cancelarem.Mantenha uma variável que comece em
0. Faça XOR com cada valor denumsnela e, em seguida, retorne-a. Não é necessário usar mapa nem ordenar.
Solução
Encontrar o único valor sem par é um problema de contagem, e um mapa hash conta cada valor em uma única passagem. O porém é a memória: um mapa cresce junto com a lista. XOR elimina a necessidade de contar, porque aplicar XOR a um valor com ele mesmo resulta em 0. Aplique XOR a todos os valores da lista e cada par se anula, deixando o único valor em uma passagem com uma variável.
Conte cada valor percorrendo
Correta, mas não termina nos maiores testes
Intuição
Pegue cada valor por vez e percorra a lista inteira para contar quantas vezes ele aparece. Um valor de um par conta 2. O valor único conta 1, então retorne o primeiro valor cuja contagem seja 1.
Isso está correto porque as contagens decorrem diretamente da definição da resposta, e não requer memória extra além de um contador.
É lento porque cada um dos n valores aciona uma varredura completa de n valores. Quando o valor único está no fim de uma lista de 9,999, isso representa quase 10^8 comparações.
Algoritmo
- Percorra cada valor em
nums. - Percorra a lista inteira e conte os valores iguais a esse valor.
- Se a contagem for 1, retorne esse valor.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Conte com um mapa de hash
Intuição
Varrer a lista novamente para cada valor repete trabalho. Conte todos os valores em uma única passagem: um mapa de hash que associa cada valor à sua contagem, em que cada etapa acrescenta 1 à contagem do valor atual.
Para [5, -2, 7, 5, 7], o mapa termina como 5 → 2, -2 → 1, 7 → 2. Uma segunda passagem pelo mapa encontra a entrada com contagem 1, que é -2.
Cada valor custa uma atualização do mapa, então o tempo é O(n). O mapa contém cerca de n/2 entradas, o que representa memória extra O(n). Em C, que não tem um mapa integrado, um array de contadores indexado por value + 10^4 desempenha o mesmo papel, pois os valores são pequenos.
Algoritmo
- Crie um mapa vazio de valores para contagens.
- Para cada valor em
nums, adicione 1 à sua contagem. - Percorra o mapa e retorne o valor cuja contagem é 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR todos os valores
Intuição
XOR compara dois números bit a bit e define um bit onde eles diferem. Disso seguem três fatos: x ^ x = 0, x ^ 0 = x e a ordem das operações não importa.
Então, aplique XOR a toda a lista em uma variável que começa em 0. Você pode reagrupar as operações para que cada par encontre seu igual, e cada par se torne 0. O que resta é 0 ^ single, que é o valor único. Para [8, 3, 8]: 0 ^ 8 = 8, depois 8 ^ 3 = 11 e, em seguida, 11 ^ 8 = 3.
Números negativos também funcionam. XOR opera sobre os bits da representação em complemento de dois, e dois números negativos iguais têm bits iguais, então se cancelam como qualquer outro par. O loop lê cada valor uma vez e mantém uma variável: tempo O(n) e memória extra O(1).
Algoritmo
- Defina
resultcomo 0. - Para cada valor em
nums, definaresultcomoresult ^ value. - Retorne
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Armadilhas e casos extremos
O loop XOR é curto, então os erros se escondem no ponto em que ele começa e nas alternativas que as pessoas escolhem.
- Começar
resultemnums[0]e depois percorrer todos os valores, incluindo o índice 0. O primeiro valor entra na operação XOR duas vezes e se cancela. Comece em 0 ou pule o índice 0. - Ordenar e comparar os vizinhos em passos de dois, depois esquecer que o valor único pode ser o último elemento. Em
[1, 1, 2], não existe nenhum par diferente, e a resposta é o 2 que sobra. - Usar
2 × sum(distinct values) - sum(nums). O resultado está correto, mas o conjunto de valores distintos custaO(n)de memória, algo que a versão com XOR evita. - Esperar que XOR funcione para outras quantidades de ocorrências. Ele cancela valores que aparecem um número par de vezes. Se um valor aparecesse três vezes, uma cópia sobraria e prejudicaria a resposta.
Perguntas frequentes3
Qual é a complexidade de tempo de Single Number?
A solução com XOR é executada em tempo O(n) e usa O(1) de espaço extra, porque lê cada valor uma vez e mantém uma variável. Um mapa hash também leva O(n) de tempo, mas precisa de O(n) de memória. Contar cada valor com uma nova varredura leva O(n²).
Por que XOR resolve o problema do número único?
Fazer XOR de um número com ele mesmo resulta em 0, fazer XOR com 0 não altera nada, e a ordem das operações não importa. Portanto, ao fazer XOR de toda a lista, cada par pode ser agrupado e se cancela, resultando em 0. Só resta o valor sem par.
O truque XOR funciona com números negativos?
Sim. XOR opera sobre os bits que armazenam o número, e os números negativos são armazenados em complemento de dois. Dois números negativos iguais têm bits idênticos, então se cancelam exatamente como os positivos. Em [5, -2, 7, 5, 7], o resultado é -2.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def singleNumber(nums):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
nums = [8, 3, 8]
Saída Esperada
3