Búsqueda de un número en una lista [duplicar]

Question

Esta pregunta ya tiene una respuesta aquí:

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

Cuál sería el mejor algoritmo para encontrar un número que sólo se produce una vez en una lista que tiene todos los otros números que ocurre exactamente dos veces.

Así, en la lista de enteros (vamos a tomar esto como una matriz) cada entero se repite exactamente el doble, a excepción de uno.Para encontrar que, ¿cuál es el mejor algoritmo.

Answer 1

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

En 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 se produce una vez.

Esto funciona porque la primera vez que se pulsa un número que marca el valor de la variable num con sí mismo, y la segunda vez que se quita la marca de num con (más o menos).El único que sigue sin marcar no es su duplicado.

Answer 2

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

Vamos a llamar a la única números a y b.Primero se toma el XOR de todo, como Kyle sugerido.Lo que tenemos es un^b.Sabemos que a^b != 0, ya que una != b.Elija cualquier 1 bit de a^b, y usar eso como una máscara-en más detalle:elegir x como una potencia de 2 por lo que x & (a^b) es distinto de cero.

Ahora dividir la lista en dos sublistas -- una sublista contiene todos los números y con y&x == 0, y el resto ir en la otra sublista.Por la forma en que elegimos x, sabemos que a y b están en cubos diferentes.También sabemos que cada par de duplicados es todavía en la misma cubeta.Así que ahora podemos aplicar ye olde "XOR-em-todos" truco a cada uno de ellos de forma independiente, y descubrir lo que a y b son completamente.

Bam.

Answer 3

O(N) en tiempo O(N) en la memoria

HT= Tabla Hash

HT.clear() repasa la lista en orden para cada elemento que ver

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

al final, el elemento de la HT es el elemento que está buscando.

La nota de crédito @Jared Updike):Este sistema se puede encontrar de todos los Impares instancias de los elementos.

---

comentario:No entiendo cómo la gente puede votar hasta las soluciones que te dan NLogN rendimiento.en la que el universo es el que "mejor" ?Incluso estoy más sorprendido que marcó el aceptado responder a s NLogN solución...

Estoy de acuerdo, sin embargo, que si la memoria no es necesario ser constante, entonces NLogN sería (hasta ahora) la mejor solución.

Answer 4

Kyle solución sería, obviamente, no coger las situaciones eran el conjunto de datos no siguen las reglas.Si todos los números en pares el algoritmo daría un resultado de cero, el mismo valor como si el cero sería el único valor con una sola ocurrencia.

Si hubo múltiple de una sola ocurrencia de valores o triples, el resultado sería errouness así.

La prueba del conjunto de datos, bien podrían acabar con una más costosa algoritmo, ya sea en la memoria o en el tiempo.

Csmba la solución no muestran algún errouness de datos (no más de una sola ocurrencia de valor), pero no otras (quadrouples).Con respecto a su solución, dependiendo de la implementación de la hta, ya sea de la memoria y/o el tiempo es más de O(n).

Si no podemos estar seguros acerca de la exactitud del conjunto de entrada, de clasificación y conteo o el uso de una tabla hash de conteo de ocurrencias con el número entero a sí mismo siendo la clave hash sería factible.

Answer 5

Yo diría que el uso de un algoritmo de ordenación y luego ir a través de la lista ordenada para encontrar el número es una buena manera de hacerlo.

Y ahora el problema es encontrar "la mejor" algoritmo de ordenación.Hay una gran cantidad de algoritmos de ordenación, cada uno de ellos con sus puntos fuertes y débiles, así que esta es una pregunta complicada.El Entrada de la Wikipedia parece ser una buena fuente de información sobre eso.

Answer 6

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

Necesita especificar a qué se refiere con "lo mejor" - para algunos, la velocidad es todo lo que importa y permitiría recibir una respuesta como "el mejor" - para otros, se podría perdonar a unos pocos cientos de milisegundos si la solución era más legible.

"Mejor" es subjetivo, a menos que usted es más específico.

---

Que dijo:

Iterar a través de los números, para cada número de búsqueda de la lista para ese número, y cuando llega al número que devuelve sólo un 1 por el número de resultados de búsqueda, son un hecho.

Answer 8

Parece que lo mejor que puedes hacer es recorrer la lista, para cada elemento que se agrega a una lista de "visto" elementos o bien eliminarlo de la "visto" si es que ya hay, y al final de su lista de "visto" en los productos que se incluyen el elemento singular.Esto es O(n) en lo que respecta a tiempo y n en cuanto a espacio (en el peor de los casos, va a ser mucho mejor si la lista está ordenada).

El hecho de que son enteros no realmente factor, ya que no hay nada especial que usted puede hacer con la adición de ellos...es allí?

Pregunta

No entiendo por qué la respuesta seleccionada es "mejor" por cualquier estándar.O(N*lgN) > O(N), y los cambios de la lista (o por el contrario, se crea una copia de la misma, que es aún más costoso en tiempo y espacio).Me estoy perdiendo algo?

Answer 9

Depende de cómo de grande/pequeño/la diversidad de los números son sin embargo.Un radix sort podría ser aplicable, el cual reducirá la ordenación del tiempo de O(N log N) solución en un alto grado.

Answer 10

El método de clasificación y la XOR método de la complejidad mismo tiempo.El XOR método es O(n) si se supone que la operación XOR bit a bit de dos cadenas es una constante de tiempo de operación.Esto es equivalente a decir que el tamaño de los enteros en la matriz a es acotado por una constante.En ese caso, usted puede utilizar Radix sort para ordenar la matriz en O(n).

Si los números no están delimitadas, a continuación, XOR bit a bit toma tiempo O(k) donde k es la longitud de la cadena de bits, y el XOR método toma O(nk).Ahora, de nuevo Radix sort ordena la matriz en tiempo O(nk).

Answer 11

Usted podría simplemente poner los elementos en el conjunto en un hash hasta encontrar una colisión.En ruby, este es un one-liner.

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

Así, find_dupe([1,2,3,4,5,1]) volvería 1.

Esto es en realidad un común "engañar" a la pregunta de la entrevista, aunque.Normalmente es acerca de una lista de enteros consecutivos con un duplicado.En este caso, el entrevistador es a menudo en busca de uso de la Gaussiana de la suma de n-enteros truco por ejemplo, n*(n+1)/2 restado de la suma real.El libro de texto de respuesta 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