Trouver un numéro unique dans une liste

Question

Quel serait le meilleur algorithme pour trouver un nombre qui ne se produit qu'une fois dans une liste qui a tous les autres numéros produisent exactement deux fois.

Ainsi, dans la liste d'entiers (permet de le prendre comme un tableau) chaque entier répète exactement deux fois, sauf un. Pour trouver celui-là, quel est le meilleur algorithme.

Answer 1

La manière la plus rapide (O(n)) et le plus efficace en terme de mémoire (O(1)) est avec l'opération 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);

Cette affiche "1", qui est le seul qui se produit une fois.

Cela fonctionne parce que la première fois que vous frappez un nombre, il marque le num variable avec elle-même, et la deuxième fois, annulé le marquage num avec lui-même (plus ou moins). Le seul qui reste non marqué est votre double non.

Answer 2

Par ailleurs, vous pouvez développer cette idée à très vite trouver deux nombres uniques parmi une liste de doublons.

Appelons l'unique nombres a et b. Prenez d'abord le XOR de tout, comme Kyle suggéré. Ce que nous obtenons est un^b. Nous savons que a^b != 0, car un != b. Choisir 1 bit de a^b, et de l'utiliser comme un masque -- en détail: choisir x comme une puissance de 2 x & (a^b) est différent de zéro.

Maintenant diviser la liste en deux sous-listes -- une sous-liste contient tous les numéros y avec y&x == 0, et le reste dans les autres sous-liste. Par le moyen que nous avons choisi de x, nous savons que a et b sont dans des compartiments différents. Nous savons aussi que chaque paire de doublons est toujours dans le même seau. Nous pouvons donc appliquer ye olde "XOR-em-all" astuce pour chaque segment de manière indépendante, et découvrir ce que a et b sont complètement.

Bam.

Answer 3

O(N) le temps, O(N) de la mémoire

HT= Table de Hachage

HT.clear() allez sur la liste dans l'ordre pour chaque élément que vous voyez

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

à la fin, l'élément de la HT est l'élément que vous recherchez.

La Note de crédit @Jared Updike): Ce système permettra de trouver toutes les occurrences d'éléments.

---

commentaire: je ne vois pas comment les gens peuvent-ils voter en place des solutions qui vous donnent NLogN performance. dans quel univers est "mieux" ? Je suis d'autant plus choqué que vous avez marqué la accepté de répondre à s NLogN solution...

Je suis d'accord, cependant, que si la mémoire est nécessaire pour être constante, alors NLogN serait (pour l'instant) la meilleure solution.

Answer 4

Je dirais que l'utilisation d'un algorithme de tri et ensuite passer par la liste triée de trouver le nombre est une bonne façon de le faire.

Et maintenant le problème est de trouver le "meilleur" algorithme de tri. Il existe beaucoup d'algorithmes de tri, chacun avec ses points forts et points faibles, donc c'est tout à fait une question complexe. L' entrée de Wikipedia semble comme une bonne source d'infos à ce sujet.