Trucos con XOR
Paso 1 de 7
acc0memoriaO(1)
8421
siguiente4
0
1
0
0
acc0
0
0
0
0
XOR pliega toda una lista en un solo acumulador. Empieza en cero; el primer valor es 4.
La idea
XOR tiene dos propiedades que hacen todo el trabajo: x ^ x es 0, y x ^ 0 es x. Además, no le importa el orden.
Así que aplica XOR a toda una lista y cada valor que aparece dos veces se borra solo. Lo que sobrevive apareció un número impar de veces, en tiempo O(n) y memoria O(1).
Ejemplo del mundo real
RAID 5 guarda un disco de paridad que es el XOR de los demás. Si pierdes cualquier disco, su contenido se reconstruye aplicando XOR a todo lo que queda: el bloque que falta es el valor que ya no tiene pareja.
El código
Te toca
Completa el espacio en blanco.
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