Truques com XOR
Passo 1 de 7
acc0memóriaO(1)
8421
próximo4
0
1
0
0
acc0
0
0
0
0
XOR dobra uma lista inteira num único acumulador. Comece em zero; o primeiro valor é 4.
A ideia
O XOR tem duas propriedades que fazem todo o trabalho: x ^ x é 0, e x ^ 0 é x. Ele também ignora a ordem.
Então aplique XOR em uma lista inteira e todo valor que aparece duas vezes se apaga. O que sobra apareceu um número ímpar de vezes — em O(n) de tempo e O(1) de memória.
Exemplo do mundo real
O RAID 5 guarda um disco de paridade que é o XOR dos outros. Perca qualquer disco e o conteúdo dele é reconstruído aplicando XOR em tudo o que restou: o bloco que falta é o valor que ficou sem par.
O código
Sua vez
Preencha a lacuna.
def single_number(nums):
acc = 0
for x in nums:
acc = acc ___ x
return acc
print(single_number([9, 5, 9])) # want 5Mini quiz
1 / 3