En una matriz con enteros, un valor está en la matriz dos veces. ¿Cómo se determina cuál?

Question

Suponga que la matriz tiene números enteros entre 1 y 1,000,000.

Sé que algunas formas populares de la solución de este problema:

1. Si se incluyen todos los números entre 1 y 1.000.000, hallar la suma de los elementos de la matriz y restar de la suma total (n * n + 1/2)
2. utilizar un mapa de hash (necesita memoria adicional)
3. utilizar un mapa de bits (menos sobrecarga de la memoria)

recientemente me encontré con otra solución y necesito un poco de ayuda en la comprensión de la lógica it:

Mantenga un solo acumulador de radix. Usted exclusivo o el acumulador con tanto el índice como el valor en ese índice.

El hecho de que x^C^x == C es útil aquí, ya que cada número será xor'd dos veces, excepto el que está allí dos veces, que aparecerá 3 veces. (x^x^x == x) Y el índice final, que aparecerá una vez. Si sembramos el acumulador con el índice final, el valor final del acumulador será el número que está en la lista dos veces.

Apreciaré si alguien puede ayudarme a entender la lógica detrás de este enfoque (¡con un pequeño ejemplo!).

Answer 1

Suponga que tiene un acumulador

int accumulator = 0; 

En cada paso de su bucle, XOR del acumulador con i y v, donde i es el índice de la iteración del bucle y v es el valor en el i º posición de la matriz.

accumulator ^= (i^v) 

Normalmente, i y v será el mismo número para que el resultado final será hacer

accumulator ^= (i^i) 

Pero i^i == 0, así que esto va a terminar siendo un no-op y el valor del acumulador no ser tocadoEn este punto, debo decir que el orden de los números en el conjunto no importa porque XOR es conmutativa, por lo que incluso si el conjunto se mezcla para comenzar con el resultado al final, todavía debería ser 0 (el valor inicial del acumulador) .

Ahora, ¿qué ocurre si un número aparece dos veces en la matriz? Obviamente, este número aparecerá tres veces en el XORing (uno para el índice igual al número, uno para la apariencia normal del número y otro para el aspecto adicional). Además, uno de los otros números solo aparecerá una vez (solo para su índice).

Esta solución ahora supone que el número que solo aparece una vez es igual al último índice de la matriz, o en otras palabras: que el rango de números en la matriz es contiguo y comienza desde el primer índice que se va a procesado (editar: gracias a caf por este comentario mano a mano, esto es lo que realmente tenía en mente, pero lo eché a perder al escribir). Con este (N aparece sólo una vez) como un dado, tenga en cuenta que a partir de

int accumulator = N; 

efectivamente hace N nuevo aparecen dos veces en la operación XOR. En este punto, nos quedan números que solo aparecen exactamente dos veces, y solo el número que aparece tres veces. Dado que los números que aparecen dos veces serán XOR a 0, el valor final del acumulador será igual al número que aparece tres veces (es decir, uno adicional).

Answer 2

La lógica es que solo tiene que almacenar el valor del acumulador, y solo tiene que pasar por la matriz una vez. Eso es bastante inteligente.

Por supuesto, si este es el mejor método en la práctica depende de la cantidad de trabajo que se necesita para calcular el tamaño exclusivo o el tamaño de la matriz. Si los valores de la matriz se distribuyen aleatoriamente, puede ser más rápido utilizar un método diferente, incluso si usa más memoria, ya que es probable que se encuentre el valor duplicado mucho antes de que se revise toda la matriz.

Por supuesto si la matriz es ordenada para empezar, las cosas son considerablemente más fáciles. Entonces, depende mucho de cómo se distribuyan los valores en toda la matriz.

Answer 3

Cada número entre 1 y 10.001 inclusive aparece como un índice de matriz. (¿No se indexan las matrices en C? Bueno, no hace la diferencia siempre que seamos consistentes sobre si los valores e índices de la matriz comienzan en 0 o ambos comienzan en 1. Iré con la matriz que comienza en 1, ya que eso es lo que parece decir la pregunta.)

De todos modos, sí, cada número entre 1 y 10.001 inclusive aparece, precisamente una vez, como un índice de matriz. Cada número entre 1 y 10,000 inclusive también aparece como un valor de matriz, exactamente una vez, con la excepción del valor duplicado que aparece dos veces. Entonces matemáticamente, el cálculo que estamos haciendo en general es el siguiente:

1 xor 1 xor 2 xor 2 xor 3 xor 3 xor ... xor 10,000 xor 10,000 xor 10,001 xor D 

donde D es el valor duplicado. Por supuesto, los términos en el cálculo probablemente no aparecen en ese orden, pero xor es conmutativo, por lo que podemos reorganizar los términos como queramos. Y n xor n es 0 para cada n. Entonces lo anterior simplifica a

10,001 xor D 

xor esto con 10,001 y obtiene D, el valor duplicado.

Answer 4

La pregunta es: ¿le interesa saber cómo hacer trucos ingeniosos pero puramente académicos con poca relevancia en el mundo real, o quiere saber esto porque en el mundo real puede escribir programas que usen matrices? Esta respuesta se dirige al último caso.

La solución sensata es recorrer todo el conjunto y ordenarlo como lo hace. Mientras ordena, asegúrese de que no haya valores duplicados, es decir, implemente el tipo de datos abstractos "establecer". Esto probablemente requerirá una segunda matriz para ser asignada y la clasificación llevará mucho tiempo. Ya sea que consuma más o menos tiempo que astutos trucos, no lo sé.

Sin embargo, lo bueno es una matriz de n valores sin ordenar a que en el mundo real? Si no están ordenadas, debemos suponer que su orden es importante de alguna manera, por lo que la matriz original debería conservarse.Si desea buscar a través de la matriz original o analizarla para duplicados, valores medios, etc., realmente desea una versión ordenada de la misma. Una vez que lo haya ordenado, puede buscarlo binariamente con "O log n".