algorithm - online - Encontrar un solo número en una lista

puzzle numeros online

Question

Esta pregunta ya tiene una respuesta aquí:

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

¿Cuál sería el mejor algoritmo para encontrar un número que aparece solo una vez en una lista que tiene todos los demás números exactamente dos veces?

Entonces, en la lista de enteros (vamos a tomarlo como una matriz), cada entero se repite exactamente dos veces, excepto uno. Para encontrarlo, ¿cuál es el mejor algoritmo?

Answer 1

Debes especificar lo que quieres decir con "lo mejor": para algunos, la velocidad es lo único que importa y calificaría una respuesta como "lo mejor"; para otros, podrían perdonar unos cientos de milisegundos si la solución fuera más legible.

"Lo mejor" es subjetivo a menos que sea más específico.

Eso dijo:

Itere a través de los números, para cada número busca en la lista para ese número y cuando alcanza el número que devuelve solo un 1 para el número de resultados de búsqueda, ha terminado.

Answer 2

Depende de qué tan grandes / pequeños / diversos sean los números. Podría aplicarse una clase de radix que reduciría en gran medida el tiempo de clasificación de la solución O (N log N).

Answer 3

El método de clasificación y el método XOR tienen la misma complejidad de tiempo. El método XOR es solo O (n) si supone que el XOR bit a bit de dos cadenas es una operación de tiempo constante. Esto es equivalente a decir que el tamaño de los enteros en la matriz está limitado por una constante. En ese caso, puede usar la clasificación Radix para ordenar la matriz en O (n).

Si los números no están acotados, entonces el bit XOR toma tiempo O (k) donde k es la longitud de la cadena de bits, y el método XOR toma O (nk). Ahora otra vez Radix sort ordenará la matriz en el tiempo O (nk).

Answer 4

Implementación en Ruby:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

Answer 5

La forma más rápida (O (n)) y más eficiente de la memoria (O (1)) es con la operación XOR.

Cª:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i/n", num);

Esto imprime "1", que es el único que ocurre una vez.

Esto funciona porque la primera vez que tocas un número marca la variable num consigo mismo, y la segunda vez marca el número consigo mismo (más o menos). El único que permanece sin marcar es tu no duplicado.

Answer 6

La solución de Kyle obviamente no captaría situaciones si el conjunto de datos no sigue las reglas. Si todos los números estuvieran en pares, el algoritmo arrojaría un resultado de cero, el mismo valor exacto que si el cero fuera el único valor con una sola ocurrencia.

Si hubiera múltiples valores únicos de ocurrencia o triples, el resultado también sería erróneo.

Probando el conjunto de datos bien podría terminar con un algoritmo más costoso, ya sea en memoria o tiempo.

La solución de Csmba muestra algunos datos de errouness (no o más de un solo valor de ocurrencia), pero no otros (cuadruplos). En cuanto a su solución, dependiendo de la implementación de HT, la memoria y / o el tiempo son más que O (n).

Si no podemos estar seguros acerca de la corrección del conjunto de entrada, clasificar y contar o usar una ocurrencia de conteo de hashtaps con el número entero como la clave de hash sería factible.

Answer 7

Parece que lo mejor que se puede hacer es repetir la lista, para cada elemento agregarlo a una lista de elementos "vistos" o eliminarlo de "visto" si ya está allí, y al final su lista de "visto" "los artículos incluirán el elemento singular. Esto es O (n) en cuanto al tiempo yn en lo que respecta al espacio (en el peor de los casos, será mucho mejor si la lista está ordenada).

El hecho de que sean enteros realmente no tiene en cuenta, ya que no hay nada especial que puedas hacer al sumarlos ... ¿verdad?

Pregunta

No entiendo por qué la respuesta seleccionada es "mejor" según cualquier estándar. O (N * lgN)> O (N), y cambia la lista (o crea una copia de la misma, que todavía es más cara en espacio y tiempo). ¿Me estoy perdiendo de algo?

Answer 8

Por cierto, puede ampliar esta idea para encontrar muy rápidamente dos números únicos entre una lista de duplicados.

Llamemos a los números únicos a y b. Primero tome el XOR de todo, como sugirió Kyle. Lo que obtenemos es a ^ b. Sabemos a ^ b! = 0, ya que a! = B. Elija cualquier 1 bit de a ^ b, y úselo como máscara: con más detalle: elija x como una potencia de 2, de modo que x & (a ^ b) sea distinto de cero.

Ahora divide la lista en dos sublistas: una sublista contiene todos los números y con y & x == 0, y el resto entra en la otra sublista. Por cierto, elegimos x, sabemos que a y b están en diferentes cubos. También sabemos que cada par de duplicados aún está en el mismo cubo. Así que ahora podemos aplicar el viejo truco de "XOR-em-all" a cada cubo de forma independiente, y descubrir qué ayb son completamente.

Bam.

Answer 9

Simplemente podría poner los elementos en el conjunto en un hash hasta que encuentre una colisión. En ruby, este es un trazador de líneas.

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

Entonces, find_dupe([1,2,3,4,5,1]) devolvería 1.

Sin embargo, esta es una pregunta de entrevista "truco" común. Normalmente se trata de una lista de enteros consecutivos con un duplicado. En este caso, el entrevistador a menudo busca que use la suma Gaussiana del truco de n- enteros, por ejemplo, n*(n+1)/2 restados de la suma real. La respuesta del libro de texto es algo como esto.

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end

Answer 10

Yo diría que usar un algoritmo de clasificación y luego revisar la lista ordenada para encontrar el número es una buena manera de hacerlo.

Y ahora el problema es encontrar el "mejor" algoritmo de clasificación. Hay muchos algoritmos de clasificación, cada uno de ellos con sus puntos fuertes y débiles, por lo que esta es una pregunta bastante complicada. La entrada de Wikipedia parece una buena fuente de información sobre eso.

Answer 11

O (N) tiempo, O (N) memoria

HT = tabla Hash

HT.clear () revisa la lista para cada elemento que veas

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

al final, el artículo en el HT es el artículo que está buscando.

Nota (crédito @Jared Updike): este sistema encontrará todas las instancias de elementos impares.

Comenta : No veo cómo la gente puede votar por soluciones que le den el rendimiento NLogN. ¿En qué universo está ese "mejor"? Estoy aún más sorprendido de que hayas marcado la respuesta aceptada de la solución NLogN ...

Sin embargo, sí estoy de acuerdo en que si se requiere que la memoria sea constante, entonces NLogN sería (hasta ahora) la mejor solución.