Comment trouver un élément dupliqué dans un tableau d'entiers consécutifs mélangés?

Update 2: certains pensent que L'utilisation de XOR pour trouver le numéro dupliqué est un piratage ou un truc. Ce à quoi ma réponse officielle est: "Je ne cherche pas un nombre de duplicata, je cherche un motif de duplicata dans un tableau de jeux de bits. Et XOR est certainement mieux adapté que D'ajouter à manipuler des ensembles de bits". :- )

mise à jour: juste pour m'amuser avant de me coucher, voici une solution alternative "one-line" qui exige zéro le stockage supplémentaire (pas même un compteur de boucle), ne touche chaque élément du réseau qu'une seule fois, est non destructif et n'est pas gradué du tout: -)

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 calculer la seconde moitié de cette expression au moment de la compilation, donc l '"algorithme" va exécuter exactement 1002 opérations.

et si les valeurs des éléments du tableau sont connues au moment de la compilation, le compilateur optimisera l'ensemble de la déclaration à une constante. :-)

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

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

à part celui-là, voici un algorithme destructeur qui peut être mis à l'échelle en toute sécurité 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 laisse l'exercice de comprendre pourquoi cela fonctionne pour vous, un simple conseil :-):

a ^ a = 0
0 ^ a = a

une version non destructive de solution par Franci Penov.

cela peut être fait en utilisant l'opérateur XOR .

disons que nous avons un tableau de taille 5 : 4, 3, 1, 2, 2

Qui sont à l'index: 0, 1, 2, 3, 4

faites maintenant un XOR de tous les éléments et de tous les indices. Nous obtenons 2 , qui est l'élément dupliqué. Ce se produit parce que, 0 ne joue aucun rôle dans l'XORing. Les indices n-1 restants se jumellent avec les mêmes éléments n-1 dans le tableau et le seul élément non apparié dans le tableau sera le dupliqué.

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ébordement qui est vu dans la solution basée sur l'addition.

Puisque c'est une question d'entrevue, il serait préférable pour commencer avec la solution à base d'addition, identifier la limite de débordement et ensuite donner la XOR solution à base de 1519110920"

cela utilise une variable supplémentaire et ne répond donc pas entièrement aux exigences de la question.

additionner tous les nombres ensemble. La somme finale sera le 1+2+...+1000+numéro en double.

pour paraphraser la solution de Francis Penov.

le problème (habituel) est: étant donné un tableau d'entiers de longueur arbitraire qui ne contiennent que des éléments répétés un temps Pair de temps à l'exception d'une valeur qui est répétée un temps Impair de temps, Découvrez cette valeur.

la solution est:

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

Votre problème actuel est une adaptation. L'astuce est que vous devez trouver l'élément qui est répété deux fois de sorte que vous nécessité d'adapter la solution pour compenser cette faiblesse.

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

C'est ce que fait la solution de François à la fin, bien qu'elle détruise tout le réseau (soit dit en passant, elle ne pouvait détruire que le premier ou le dernier élément...)

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

Il aurait été formulé plus précisément s'ils avaient eu besoin d'espace O(1) (1000 peut être vu comme N Car c'est arbitraire ici).

additionner tous les numéros. La somme des nombres entiers de 1..1000 (1000*1001)/2. La différence entre ce que vous obtenez est votre numéro.

si vous savez que nous avons les nombres exacts 1-1000, vous pouvez additionner les résultats et soustraire 500500 ( sum(1, 1000) ) du total. Cela donnera le nombre répété parce que sum(array) = sum(1, 1000) + repeated number .

Eh bien, il y a une façon très simple de le faire... chacun des nombres entre 1 et 1000 se produit exactement une fois, sauf pour le numéro est répété.... donc, la somme de 1....1000, c'est 500500. Donc, l'algorithme est:

sum = 0
for each element of the array:
   sum += that element of the array
number_that_occurred_twice = sum - 500500

Une solution en ligne en Python

arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -> 2

la réponse de @Matthieu M. explique pourquoi cela fonctionne .

n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s

public static void main(String[] args) {
    int start = 1;
    int end = 10;
    int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
    System.out.println(findDuplicate(arr, start, end));
}

static int findDuplicate(int arr[], int start, int end) {

    int sumAll = 0;
    for(int i = start; i <= end; i++) {
        sumAll += i;
    }
    System.out.println(sumAll);
    int sumArrElem = 0;
    for(int e : arr) {
        sumArrElem += e;
    }
    System.out.println(sumArrElem);
    return sumArrElem - sumAll;
}

Aucune exigence supplémentaire de stockage (à l'exception de la variable de boucle).

int length = (sizeof array) / (sizeof array[0]);
for(int i = 1; i < length; i++) {
   array[0] += array[i];
}

printf(
    "Answer : %d\n",
    ( array[0] - (length * (length + 1)) / 2 )
);

Faire des arguments et des piles d'appels comptent comme des auxiliaires de stockage?

int sumRemaining(int* remaining, int count) {
    if (!count) {
        return 0;
    }
    return remaining[0] + sumRemaining(remaining + 1, count - 1);
}

printf("duplicate is %d", sumRemaining(array, 1001) - 500500);

Edit: appel tail version

int sumRemaining(int* remaining, int count, int sumSoFar) {
    if (!count) {
        return sumSoFar;
    }
    return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]);
}
printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500);

public int duplicateNumber(int[] A) {
    int count = 0;
    for(int k = 0; k < A.Length; k++)
        count += A[k];
    return count - (A.Length * (A.Length - 1) >> 1);
}

un nombre de triangle T(n) est la somme des N nombres naturels de 1 à N. Elle peut être représentée par n(n+1)/2. Ainsi, sachant que parmi 1001 nombres naturels donnés, un et un seul nombre est dupliqué, vous pouvez facilement additionner tous les nombres donnés et soustraire T(1000). Le résultat contiendra ce double.

pour un nombre triangulaire T (n), Si n est une puissance de 10, Il y a aussi une belle méthode pour trouver ce T(n), basé sur la représentation de base-10:

n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s

je soutiens l'addition de tous les éléments, puis en soustrayant de la somme de tous les indices, mais cela ne fonctionnera pas si le nombre d'éléments est très grand. C'est-à-dire: Il causera un débordement d'entier! J'ai donc conçu cet algorithme qui peut être va réduire les chances d'un débordement entier dans une large mesure.

   for i=0 to n-1
        begin:  
              diff = a[i]-i;
              dup = dup + diff;
        end
   // where dup is the duplicate element..

mais par cette méthode Je ne pourrai pas trouver l'index auquel l'élément dupliqué est présent!

Pour cela je dois traverser le tableau un autre temps qui n'est pas souhaitable.

amélioration de la réponse de Fraci basée sur la propriété des valeurs consécutives XORing:

int result = xor_sum(N);
for (i = 0; i < N+1; i++)
{
   result = result ^ array[i];
}

où:

// Compute (((1 xor 2) xor 3) .. xor value)
int xor_sum(int value)
{
    int modulo = x % 4;
    if (modulo == 0)
        return value;
    else if (modulo == 1)
        return 1;
    else if (modulo == 2)
        return i + 1;
    else
        return 0;
}

Ou en pseudo-code/math lang f(n) (optimisé):

if n mod 4 = 0 then X = n
if n mod 4 = 1 then X = 1
if n mod 4 = 2 then X = n+1
if n mod 4 = 3 then X = 0

et sous forme canonique f(n) est:

f(0) = 0
f(n) = f(n-1) xor n

ma réponse à la question 2:

trouver la somme et le produit des nombres de 1 -(À) N, dire SUM , PROD .

trouver la somme et le produit des nombres de 1 - N-x-y, (supposer x, y manquant), dire mySum, myProd,

ainsi:

SUM = mySum + x + y;
PROD = myProd* x*y;

ainsi:

x*y = PROD/myProd; x+y = SUM - mySum;

nous pouvons trouver x,y si résoudre cette équation.