Trouver un seul numéro dans une liste [doublon]
https://stackoverflow.com/questions/35185
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Cette question a déjà une réponse ici :
Quel serait le meilleur algorithme pour trouver un nombre qui n'apparaît qu'une seule fois dans une liste dont tous les autres nombres apparaissent exactement deux fois.
Ainsi, dans la liste des entiers (prenons-la comme un tableau), chaque entier se répète exactement deux fois, sauf un.Pour trouver celui-là, quel est le meilleur algorithme.
La solution
Le moyen le plus rapide (O(n)) et le plus efficace en mémoire (O(1)) consiste à utiliser 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);
Ceci imprime "1", qui est le seul qui apparaît une fois.
Cela fonctionne parce que la première fois que vous frappez un nombre, il marque la variable num avec elle-même, et la deuxième fois, il décoche num avec elle-même (plus ou moins).Le seul qui ne reste pas marqué est votre non-doublon.
Autres conseils
D’ailleurs, vous pouvez développer cette idée pour trouver très rapidement deux numéros uniques parmi une liste de doublons.
Appelons les nombres uniques a et b.Prenez d’abord le XOR de tout, comme Kyle l’a suggéré.Ce que nous obtenons est a^b.Nous savons a^b != 0, puisque a != b.Choisissez n'importe quel bit de a^b et utilisez-le comme masque - plus en détail :choisissez x comme puissance de 2 pour que x & (a^b) soit différent de zéro.
Divisez maintenant la liste en deux sous-listes : une sous-liste contient tous les nombres y avec y&x == 0, et le reste va dans l'autre sous-liste.D’après la façon dont nous avons choisi x, nous savons que a et b se trouvent dans des compartiments différents.Nous savons également que chaque paire de doublons se trouve toujours dans le même compartiment.Nous pouvons donc maintenant appliquer la vieille astuce "XOR-em-all" à chaque compartiment indépendamment et découvrir ce que sont complètement a et b.
Boum.
Temps O(N), mémoire O(N)
HT= Table de hachage
Ht.clear () Reposez la liste pour chaque élément que vous voyez
if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)
à la fin, l'article dans le HT est l'article que vous recherchez.
Remarque (crédit @Jared Updike) :Ce système trouvera toutes les instances impaires d'objets.
commentaire:Je ne vois pas comment les gens peuvent voter pour des solutions qui vous offrent des performances NLogN.dans quel univers est-ce "meilleur" ?Je suis encore plus choqué que vous ayez marqué la solution NLogN de la réponse acceptée...
Je suis cependant d'accord que si la mémoire doit être constante, alors NLogN serait (jusqu'à présent) la meilleure solution.
La solution de Kyle ne permettrait évidemment pas de détecter les situations dans lesquelles l'ensemble de données ne respecte pas les règles.Si tous les nombres étaient par paires, l’algorithme donnerait un résultat nul, exactement la même valeur, comme si zéro était la seule valeur à occurrence unique.
S'il y avait plusieurs valeurs d'occurrence simples ou triples, le résultat serait également une erreur.
Tester l’ensemble de données pourrait bien aboutir à un algorithme plus coûteux, soit en mémoire, soit en temps.
La solution de Csmba affiche certaines données d'erreur (pas ou plus d'une seule valeur d'occurrence), mais pas d'autres (quadruples).Concernant sa solution, selon l'implémentation de HT, soit la mémoire et/ou le temps sont supérieurs à O(n).
Si nous ne pouvons pas être sûrs de l'exactitude de l'ensemble d'entrée, le tri et le comptage ou l'utilisation d'une table de hachage comptant les occurrences avec l'entier lui-même étant la clé de hachage seraient tous deux réalisables.
Je dirais qu'utiliser un algorithme de tri puis parcourir la liste triée pour trouver le numéro est une bonne façon de le faire.
Et maintenant, le problème est de trouver « le meilleur » algorithme de tri.Il existe de nombreux algorithmes de tri, chacun avec ses points forts et ses points faibles, c'est donc une question assez compliquée.Le Entrée Wikipédia cela semble être une bonne source d'informations à ce sujet.
Implémentation 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
Vous devez préciser ce que vous entendez par "meilleur" - pour certains, la vitesse est tout ce qui compte et qualifierait une réponse de "meilleure" - pour d'autres, ils pourraient pardonner quelques centaines de millisecondes si la solution était plus lisible.
"Le meilleur" est subjectif, sauf si vous êtes plus précis.
Cela dit:
Parcourez les nombres, pour chaque numéro, recherchez ce numéro dans la liste et lorsque vous atteignez le nombre qui ne renvoie qu'un 1 pour le nombre de résultats de recherche, vous avez terminé.
Il semble que le mieux que vous puissiez faire est de parcourir la liste, pour chaque élément, ajoutez-le à une liste d'éléments "vus" ou bien supprimez-le du "vu" s'il est déjà là, et à la fin votre liste d'éléments "vus". " Les éléments incluront l'élément singulier.C'est O(n) en ce qui concerne le temps et n en ce qui concerne l'espace (dans le pire des cas, ce sera bien mieux si la liste est triée).
Le fait qu'il s'agisse de nombres entiers n'est pas vraiment pris en compte, car vous ne pouvez rien faire de spécial en les additionnant...y a-t-il?
Question
Je ne comprends pas pourquoi la réponse sélectionnée est « la meilleure » selon n'importe quelle norme.O(N*lgN) > O(N), et cela change la liste (ou bien en crée une copie, ce qui est encore plus coûteux en espace et en temps).Est-ce que j'ai raté quelque chose ?
Cela dépend cependant de la taille, de la taille et de la diversité des chiffres.Un tri par base pourrait être applicable, ce qui réduirait considérablement le temps de tri de la solution O (N log N).
La méthode de tri et la méthode XOR ont la même complexité temporelle.La méthode XOR n'est que O(n) si vous supposez que le XOR au niveau du bit de deux chaînes est une opération à temps constant.Cela équivaut à dire que la taille des entiers du tableau est limitée par une constante.Dans ce cas, vous pouvez utiliser le tri Radix pour trier le tableau en O(n).
Si les nombres ne sont pas limités, alors XOR au niveau du bit prend le temps O(k) où k est la longueur de la chaîne de bits, et la méthode XOR prend O(nk).Maintenant encore, le tri Radix triera le tableau dans le temps O(nk).
Vous pouvez simplement mettre les éléments de l'ensemble dans un hachage jusqu'à ce que vous trouviez une collision.En Ruby, il s'agit d'un one-liner.
def find_dupe(array)
h={}
array.detect { |e| h[e]||(h[e]=true; false) }
end
Donc, find_dupe([1,2,3,4,5,1]) renverrait 1.
Il s'agit en fait d'une question « piège » courante en entretien.Il s'agit normalement d'une liste d'entiers consécutifs avec un double.Dans ce cas, l'enquêteur vous demande souvent d'utiliser la somme gaussienne de n-astuce des nombres entiers, par ex. n*(n+1)/2 soustrait de la somme réelle.La réponse du manuel ressemble à ceci.
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
