Dada una matriz sin clasificar que contiene un número impar de ocurrencias para todos los números, excepto un número, ¿cómo se puede encontrar ese número?

Supongo que el problema se refiere a todos los números en la matriz, en lugar de literalmente “todos los números” (aunque esta suposición se puede reemplazar con una suposición más débil, entonces todos los números representan todos los números de 32 bits, especialmente cuando se da cuenta de que 0 es par )

Si está seguro de que hay exactamente un número repetido un número impar de veces, entonces la solución de Loi Luu es más eficiente. Puedes ver esto de una de dos maneras. Si está dispuesto a tomar como un axioma que XOR mantiene las propiedades conmutativas y asociativas, entonces puede reorganizar los términos sin cambiar el valor del producto, y al menos uno de esos reordenamientos es el término extraño XOR’ed con pares de términos cero . Si no está dispuesto a asumir eso, puede seguir el valor de cada bit a través de la cadena de xors y los bits que ocurren un número impar de veces son exactamente los que están en el término impar.

Sin embargo, si no confía tanto en sus usuarios *, puede resolver el problema en el espacio O (N), como señala Ilia. De hecho, me gustan más estas soluciones desde una perspectiva práctica, aunque son menos inteligentes.

La versión simple de esto supone que sus números son pequeños en comparación con el tamaño de su memoria y de un tamaño comparable o menor a su lista. Simplemente cree una matriz que abarque desde el número más pequeño posible hasta el más grande inicializado a cero. Para cada número (N) en la lista, cambie el enésimo bit en la matriz entre 0 y 1. Si los números no están acotados, esto se convierte en la solución de Ilia. Señalaré que O (N) aquí se refiere al tamaño de la tabla o de la tabla hash, no al tamaño de la lista, que se permite que sea mucho mayor siempre y cuando solo almacenemos la paridad.

Una solución [matemática] \ Theta (N) [/ matemática], que también requiere espacio [matemática] \ Theta (N) [/ matemática]:
Escanee la matriz y realice un seguimiento de la paridad (no del recuento real, ya que solo nos importa si es par o impar) del recuento de cada número. Use un diccionario para las actualizaciones de paridad O (1) amortizadas.

El algoritmo se da a continuación:

Dado un conjunto no ordenado A,
Deje D ser un diccionario vacío

# Rellenar un diccionario
#esto sucede N veces para una matriz de N elementos.
Para cada número n en A:
si n no es una clave en D:
D [n] = falso
#esto lleva tiempo amortizado [math] O (1) [/ math] para una tabla hash
más:
D [n] = no D [n]
# [matemáticas] O (1) [/ matemáticas]

# Ahora el diccionario contiene la paridad de conteos de todos los n en A.
# La asignación de teclas a “verdadero” se produce un número par de veces.
# Escanee por la primera aparición de un “verdadero” y devuelva esa clave.
Para cada n en A:
si D [n] es verdadero:
volver n

# El enunciado del problema garantiza que un número ocurra un número par de veces, por lo que esta línea no se puede alcanzar
afirmar inalcanzable

actualización: esta respuesta es para el problema cuando todos los números tienen un número par de ocurrencias excepto uno.
Una solución simple es así:

x = a [0]
para i = 1 a n-1:
x = x XOR a [i]

El valor de x es el número que desea encontrar. Este algoritmo no puede decirle qué posición en la matriz que contiene x.
Explicación: Es muy simple, tenemos la regla [math] \ oplus [/ math] (XOR):
[matemáticas] i \ oplus j = 0 [/ matemáticas] iff [matemáticas] i == j [/ matemáticas] y [matemáticas] i \ oplus j = 1 [/ matemáticas] de lo contrario. Entonces, [math] \ oplus [/ math] de todos los números de valores no individuales nos da 0, y tenemos [math] 0 \ oplus x = x \ forall x [/ math]