Búsqueda número entero que no ocurre dos veces en una serie

Question

que estoy tratando de resolver este problema: En una matriz de enteros todos los números se producen exactamente el doble, a excepción de un número único, que se produce exactamente una vez.

Una solución simple es para ordenar la matriz y luego probar para la no repetición. Pero estoy buscando una mejor solución que tenga una complejidad temporal de O (n).

Answer 1

Puede usar la operación "XOR" en toda la matriz. Cada par de números se cancelarán entre sí, dejándote el valor buscado.

int get_orphan(int const * a, int len) 
{ 
    int value = 0; 
    for (int i = 0; i < len; ++i) 
     value ^= a[i]; 

    // `value` now contains the number that occurred odd number of times. 
    // Retrieve its index in the array. 
    for (int i = 0; i < len; ++i) 
    { 
     if (a[i] == value) 
      return i; 
    } 

    return -1; 
}