Número que se produce sólo una vez en la matriz

Question

Duplicar posible:
Finding a single number in a list

Dada una matriz de números, a excepción de un número de todos los demás, ocurren dos veces. ¿Cuál debería ser el algoritmo para encontrar ese número que aparece solo una vez en la matriz ?

Ejemplo

a[1..n] = [1,2,3,4,3,1,2] 

debe devolver 4

Answer 1

Deje que el número que ocurre sólo una vez en la matriz sea x

x <- a[1] 
for i <- 2 to n 
    x <- x^a[i] 
return x 

Desde a^a = 0 y a^0 = a

números que se dan en pares cancelan y el resultado se almacena en x

código de trabajo en C++

#include <iostream> 

template<typename T, size_t N> 
size_t size(T(&a)[N]) 
{ 
    return N; 
} 
int main() 
{ 
    int a [] = {1,2,3,4,3,1,2}; 
    int x = a[0]; 
    for (size_t i = 1; i< size(a) ; ++i) 
    { 
     x = x^a[i]; 
    } 
    std::cout << x; 
} 

Answer 2

1. crear nuevas int i = 0
2. XOR cada elemento con i
3. Después de todas las iteraciones no se espera que el número de i

Answer 3

Bien Yo sólo sé de la fuerza de algo Bruto y es para atravesar gama entera y comprobar

Código será como (en C#):

k=0; 
for(int i=0 ; i < array.Length ; i++) 
{ 
    k ^= array[i]; 
} 
return k; 

Answer 4

Usted puede ordenar la matriz y luego encontrar el primer elemento que doesn No tengo un par. Eso requeriría varios bucles para clasificar y un bucle para encontrar el elemento individual.

Pero un método simplier sería establecer las teclas dobles a cero o un valor que no es posible en el formato actual. Depende también del lenguaje de programación, ya que no puede cambiar los tipos de clave en C++ a diferencia de C#. respuesta

Answer 5

zerkms' en C++

int a[] = { 1,2,3,4,3,1,2 }; 

int i = std::accumulate(a, a + 7, 0, std::bit_xor<int>()); 

Answer 6

Si usted tiene cantidades que no pueden ser XORed razonable (Grandes números enteros o números representan como cadenas, por ejemplo), un enfoque alternativo, que también es O (n), (pero O (n) espacio en lugar de O (1) espacio) sería simplemente usar una tabla hash. El algoritmo se parece a:

Create a hash table of the same size as the list 
For every item in the list: 
    If item is a key in hash table 
     then remove item from hash table 
     else add item to hash table with nominal value 
At the end, there should be exactly one item in the hash table 

lo haría código, C o C++, pero ninguno de ellos ha tablas hash construido en (No me pregunte por qué C++ no tiene una tabla hash en el STL,. pero tiene un mapa hash basado en un árbol rojo-negro, porque no tengo idea de lo que estaban pensando.) Y, desafortunadamente, no tengo un compilador C# a mano para probar los errores de sintaxis, así que te doy Código Java Es bastante similar, sin embargo.

import java.util.Hashtable; 
import java.util.List; 

class FindUnique { 
    public static <T> T findUnique(List<T> list) { 
     Hashtable<T,Character> ht = new Hashtable<T,Character>(list.size()); 
     for (T item : list) { 
      if (ht.containsKey(item)) { 
       ht.remove(item); 
      } else { 
       ht.put(item,'x'); 
      } 
     } 
     return ht.keys().nextElement(); 
    } 
}