Single Number

Q: 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²) .

Q: 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.

Q: 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.

Q: Como resolver isso quando os outros valores aparecem três vezes?

XOR cancela pares, não trios, então falha nesse caso. Em vez disso, conte quantos valores têm cada um dos 32 bits definido. Para cada bit, essa contagem módulo 3 é o bit do valor único, porque os trios adicionam múltiplos de 3. Isso ainda é executado em tempo O(n) com memória extra O(1) .

FácilManipulação de bits

+10

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

singleNumber(nums: integer-array) → integer

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 < 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
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.

+13 testes ocultos ao enviar

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.

0 de 3 abertas

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 0

Conte 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 0

XOR 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 result como 0.
Para cada valor em nums, defina result como result ^ 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 result em nums[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 custa O(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 frequentes4

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.

Como resolver isso quando os outros valores aparecem três vezes?

XOR cancela pares, não trios, então falha nesse caso. Em vez disso, conte quantos valores têm cada um dos 32 bits definido. Para cada bit, essa contagem módulo 3 é o bit do valor único, porque os trios adicionam múltiplos de 3. Isso ainda é executado em tempo O(n) com memória extra O(1).

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [8, 3, 8]

Esperado

Single Number

Função

Restrições

Exemplos

Dicas

Solução

Conte cada valor percorrendo

Conte com um mapa de hash

XOR todos os valores

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos