Algoritmo para encontrar un número que ocurre sólo una vez en una matriz, dadas todas se den los otros números dos veces

Question

Lo que ocurre es:

Algo:

1. tiene una tabla de hash que almacenará la número y su cuenta asociada
2. Analice la matriz e incremente el recuento para el número.
3. Ahora analizar la tabla hash para obtener el número cuyo recuento es 1.

Pueden ustedes pensar en una solución mejor que esto. Con tiempo de ejecución de O (n) y sin espacio adicional

Answer 1

Una respuesta en Ruby, en el supuesto de un producto único, y todos los demás exactamente dos apariciones:

def singleton(array) 
    number = 0 
    array.each{|n| number = number^n} 
    number 
end 

irb(main):017:0> singleton([1, 2, 2, 3, 1]) 
=> 3 

^es el operador XOR bit a bit, por cierto. XOR todo! HAHAHAH!

Rampion- me ha recordado el método de inyección, por lo que se puede hacer esto en una sola línea:

def singleton(array) array.inject(0) { |accum,number| accum^number }; end 

Answer 2

"Analice la matriz e incremente el recuento de número".

Puede cambiar esto a "Analizar la matriz y si el número ya existe en la tabla hash, elimine el número de la tabla hash". A continuación, el paso 3 es simplemente "conseguir el único número que permanece en la tabla hash"

Answer 3

Algo 2:

1. ordenar la matriz.
2. Ahora analicemos la matriz y si 2 números consecutivos no son iguales obtenemos nuestro número.
3. Esto no va a utilizar el espacio adicional

Answer 4

Esto no encaja en el proyecto de ley de "espacio extra", pero se cortará el espacio a menos que los números están ordenados de una manera determinada.

En Python:

arr = get_weird_array() 
hash = {} 

for number in arr: 
    if not number in hash: 
    hash[number] = 1 
    else: 
    del hash[number] 

for key in hash: 
    print key 

Answer 5

estoy robando Michael Sofaer's answer y reimplementar en Python y C:

Python:

def singleton(array): 
    return reduce(lambda x,y:x^y, array) 

C:

int32_t singleton(int32_t *array, size_t length) 
{ 
    int32_t result = 0; 
    size_t i; 
    for(i = 0; i < length; i++) 
     result ^= array[i]; 
    return result; 
} 

Por supuesto, la versión C está limitada a enteros de 32 bits (que pueden cambiarse trivialmente a enteros de 64 bits si así lo desea). La versión de Python no tiene tal limitación.

Answer 6

Asumiendo que puede XOR los números, que es la clave aquí, creo, por las siguientes propiedades:

• XOR es conmutativa y asociativa (por lo que el orden en el que se hace es irrelevante).
• un número XOR ed consigo mismo siempre será cero.
• cero XOR ed con un número será ese número.

Por lo tanto, si simplemente XOR todos los valores juntos, todos los que ocurren dos veces se anulan entre sí (dando 0) y el número restante (n) se XOR con ese resultado (0) a dar n.

r = 0 
for i = 1 to n.size: 
    r = r xor n[i] 
print "number is " + r 

No hay ninguna tabla hash que necesita, esto tiene O (n) el rendimiento y O (1) espacio adicional (sólo un minúsculo número entero).

Answer 7

he aquí una solución en Python que late el rubí para el tamaño (y la legibilidad también, OMI):

singleton = lambda x: reduce(operator.xor, x) 

Answer 8

Python 3.1 Solución:

>>> from collections import Counter 
>>> x = [1,2,3,4,5,4,2,1,5] 
>>> [value for value,count in Counter(x).items() if count == 1 ][0] 
3 
>>> 

• arroz.

Answer 9

Dada una matriz de enteros, cada elemento aparece dos veces, excepto uno. Encuentra ese solo. Podemos usar la operación XOR. Como cada número XOR en sí mismo, los resultados serán cero. Entonces XORamos todos los números enteros en la matriz, y el resultado es el único que queremos encontrar. Aquí es el código de la versión de Java:

public class Solution { 
    public int singleNumber(int[] A) { 
     int res=0; 
     for(int i=0;i<A.length;i++){ 
      res=res^A[i]; 
     } 
     return res; 
    } 
} 

Seguimiento 1: Dada una matriz de enteros, cada elemento aparece tres veces a excepción de uno. Encuentra ese solo. Nota: Su algoritmo debe tener una complejidad de tiempo de ejecución lineal. ¿Podrías implementarlo sin usar memoria extra? Para este problema, no podemos usar la operación XOR. La mejor manera de resolver este problema es usar "bit count". Cree un recuento de arrays de 32 int de longitud [32]. count [i] significa cuántos '1' en el i-ésimo bit de todos los enteros. Si el recuento [i] se podría dividir por 3, entonces no hacemos caso de este bit, de lo sacamos este bit y formamos la result.Below es el código de la versión de Java:

public class Solution { 
    public int singleNumber(int[] A) { 
     int res=0; 
     int[] count=new int[32]; 
     for(int i=0;i<32;i++){ 
      for(int j=0;j<A.length;j++){ 
       if(((A[j]>>i)&1)==1){ 
        count[i]=count[i]+1; 
       } 
      } 
      if((count[i]%3)!=0){ 
       res=res|(1<<i); 
      } 
     } 
     return res; 
    } 
} 

Seguimiento 2: Teniendo en cuenta una serie de enteros, cada elemento aparece dos veces excepto dos. Encuentra eso dos enteros. Solución: Primero, XOR todos los enteros de la matriz podemos obtener un resultado. (Supongamos que es c) Segundo, desde el bit menos significativo al más significativo, encuentre la primera posición '1' (suponga que la posición es pag). En tercer lugar, dividimos los enteros en dos grupos, la posición p es '1' en un grupo, '0' en otro grupo. En cuarto lugar, XOR todos los enteros en los dos grupos, y los resultados son los dos enteros que queremos.