Comment trouver un élément en double dans un tableau d’entiers consécutifs mélangées ?

Question

Je suis récemment tombé sur une question quelque part:

Supposons que vous disposez d'un tableau de 1001 entiers. Les entiers sont dans un ordre aléatoire, mais vous savez tous les entiers entre 1 et 1000 (inclus). En outre, chaque numéro s'affiche qu'une seule fois dans le tableau, sauf pour un certain nombre, qui se produit deux fois. Supposons que vous pouvez accéder à chaque élément du tableau qu'une seule fois. Décrire un algorithme pour trouver le certain nombre. Si vous avez utilisé auxiliaire de stockage dans votre algorithme, pouvez-vous trouver un algorithme qui n'en a pas besoin?

Ce que je veux savoir, c'est la deuxième partie, c'est à dire, sans l'aide d'auxiliaires de stockage. Avez-vous une idée?

Answer 1

Juste ajouter tout et soustraire le total que vous attendez si seulement les numéros de 1001 servaient de celle.

Par exemple :

Answer 2

Mise à jour 2: Certaines personnes pensent que l'utilisation de XOR pour trouver le numéro en double est un hack et astuce. À laquelle ma réponse officielle est: "je ne suis pas à la recherche d'un numéro en double, je suis à la recherche pour un double motif dans un tableau des ensembles de bits. Et XOR est certainement adapté de mieux que d'AJOUTER à manipuler des ensembles de bits". :-)

Mise à jour: Juste pour le plaisir avant d'aller me coucher, voici "on-line" solution alternative qui ne nécessite aucun stockage supplémentaire (même pas un compteur de boucle), touche chaque élément du tableau qu'une seule fois, est non destructif et n'est pas adaptée à tous :-)

printf("Answer : %d\n",
           array[0] ^
           array[1] ^
           array[2] ^
           // continue typing...
           array[999] ^
           array[1000] ^
           1 ^
           2 ^
           // continue typing...
           999^
           1000
      );

Notez que le compilateur va effectivement calculer la seconde moitié de cette expression au moment de la compilation, l ' "algorithme" va exécuter exactement 1002 opérations.

Et si l'élément de tableau de valeurs sont connues au moment de la compilation, le compilateur d'optimiser l'intégralité de la déclaration d'une constante. :-)

Solution originale: Qui ne répond pas aux exigences strictes des questions, même si cela fonctionne pour trouver la bonne réponse. Il utilise un entier supplémentaire de garder le compteur de la boucle, et elle accède à chaque élément du tableau à trois reprises, deux fois à le lire et à l'écrire à l'itération en cours et une fois à lire pour la prochaine itération.

Eh bien, vous avez besoin d'au moins une variable supplémentaire (ou un PROCESSEUR inscrire) pour stocker l'index de l'élément courant que vous allez à travers le tableau.

Hormis celle-ci, voici un destructeur algorithme qui peut en toute sécurité à l'échelle pour tout N jusqu'à MAX_INT.

for (int i = 1; i < 1001; i++)
{
   array[i] = array[i] ^ array[i-1] ^ i;
}

printf("Answer : %d\n", array[1000]);

Je vais laisser l'exercice de comprendre pourquoi cela fonctionne pour vous, un simple conseil :-):

a ^ a = 0
0 ^ a = a

Answer 3

Un non destructifs version de la solution par Franci Penov.

Cela peut être fait en faisant usage de l' XOR de l'opérateur.

Disons que nous avons un tableau de taille 5: 4, 3, 1, 2, 2
Qui sont à l'index: 0, 1, 2, 3, 4

Maintenant faire un XOR de tous les éléments et tous les indices. Nous obtenons 2, ce qui est le double de l'élément. Cela se produit parce que, 0 ne joue aucun rôle dans la XORing. Le reste n-1 indices de paire avec le même n-1 éléments dans le tableau et le seul non appariés élément du tableau sera le double.

int i;
int dupe = 0;
for(i=0;i<N;i++) {
 dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.

La meilleure caractéristique de cette solution est qu'elle ne souffre pas de problèmes de dépassement que l'on voit à la base de la solution.

Puisque c'est une question d'entrevue, il serait préférable de commencer avec les plus solution d'identifier le dépassement de la limitation et de donner ensuite l' XOR solution à base d' :)

Cela rend l'utilisation d'une variable supplémentaire n'a donc pas de répondre aux exigences de la question complètement.

Answer 4

Additionnez tous les chiffres. La somme finale sera le 1 +2 +... +1000 + numéro en double.

Answer 5

Pour paraphraser François Penov de la solution.

L' (d'habitude) le problème est le suivant: étant donné un tableau d'entiers de longueur arbitraire qui ne contiennent que des éléments répétés d'un même temps de temps, sauf une qui est répété un des moments étranges de temps, de trouver cette valeur.

La solution est:

acc = 0
for i in array: acc = acc ^ i

Votre problème actuel est une adaptation. Le truc, c'est que vous êtes de trouver l'élément qui est répété deux fois, donc il faut adapter la solution pour compenser cette faiblesse.

acc = 0
for i in len(array): acc = acc ^ i ^ array[i]

Qui est ce que François solution n'est en fin de compte, bien qu'il détruit l'ensemble de la baie (de toute façon, il ne pouvait détruire le premier ou le dernier élément...)

Mais puisque vous avez besoin de plus de stockage pour l'indice, je pense que vous serez pardonné si vous utilisez également un supplément entier... La restriction est plus probablement parce qu'ils veulent vous empêcher d'utiliser un tableau.

Il aurait été formulée avec plus de précision si ils avaient exigé O(1) de l'espace (1000 peut être vu comme N puisque c'est arbitraire ici).