algorithm - resueltos - Algoritmo para encontrar un número que aparece solo una vez en una matriz, dado que todos los demás números aparecen dos veces

numero mayor de un arreglo pseint

Question

Esta pregunta ya tiene una respuesta aquí:

• Cómo encontrar el único número en una matriz que no aparece dos veces [duplicar] 5 respuestas

Lo que puedo pensar es:

Algo

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

¿Pueden ustedes pensar en una solución mejor que esto? Con O (n) runtime y sin espacio extra

Answer 1

"Analizar la matriz e incrementar la cuenta para el número".

Podría 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". Luego, el paso 3 es simplemente "obtener el único número que permanece en la tabla hash"

Answer 2

Algo 2:

1. Ordenar la matriz.
2. Ahora analice la matriz y si 2 números consecutivos no son los mismos, obtendremos nuestro número.
3. Esto no usará espacio extra

Answer 3

Aquí hay una solución en Python que vence a la de Ruby por tamaño (y también legibilidad, IMO):

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

Answer 4

Dada una matriz de enteros, cada elemento aparece dos veces excepto uno. Encuentra ese solo. Podemos utilizar la operación XOR. Debido a que cada número XOR en sí, los resultados serán cero. Entonces XORRAMOS todos los enteros de la matriz, y el resultado es el único que queremos encontrar. Aquí está 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, excepto 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 el "conteo de bits". Cree un recuento de arreglos int 32 de longitud [32]. cuenta [i] significa cuántos ''1'' en el bit i de todos los enteros. Si el recuento [i] se puede dividir por 3, ignoramos este bit, de lo contrario, eliminamos este bit y formamos el resultado. A continuación se muestra 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: dada una matriz de enteros, cada elemento aparece dos veces, excepto dos. Encuentra que dos enteros. Solución: Primero, XOR todos los enteros en la matriz podemos obtener un resultado. (Suponga que es c) Segundo, desde el bit menos significativo hasta el bit más significativo, encuentre la primera posición ''1'' (suponga que la posición es p). Tercero, dividiendo los enteros en dos grupos, la posición p es ''1'' en un grupo, ''0'' en otro grupo. Cuarto, XOR todos los enteros en los dos grupos, y los resultados son los dos enteros que queremos.

Answer 5

Esto no se ajusta a la factura por "sin espacio adicional", pero recortará el espacio a menos que los números se ordenen de cierta manera.

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 6

Estoy robando la respuesta de Michael Sofaer y reimplementándola en Python y C:

Pitón:

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

DO:

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 se pueden cambiar de forma trivial a enteros de 64 bits si así lo desea). La versión de Python no tiene tal limitación.

Answer 7

Solución Python 3.1:

>>> 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
>>>

• Arrozal.

Answer 8

Suponiendo que puedes XOR los números, esa es la clave aquí, creo, debido a las siguientes propiedades:

• XOR es conmutativo y asociativo (por lo tanto, el orden en que se hace es irrelevante).
• un número XOR ed con sí mismo siempre será cero.
• cero XOR ed con un número será ese número.

Entonces, si simplemente XOR todos los valores juntos, todos los que ocurren dos veces se cancelarán mutuamente (dando 0) y el número restante ( n ) XOR con ese resultado (0) para dar n .

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

No se necesita tabla hash, esto tiene un rendimiento O (n) y un espacio adicional O (1) (solo un pequeño y pequeño entero).

Answer 9

Una respuesta en Ruby, asumiendo un singleton, y todas las 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 a nivel de bit, por cierto. XOR todo! ¡HAHAHAH!

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

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