Comment trouver un double élément dans un tableau de déplacés nombres entiers consécutifs?

Juste ajouter tout en haut, et soustraire le montant total que vous attendez si seulement 1001 numéros ont été utilisés à partir de cela.

Par exemple:

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2

Non destructive version de la solution par Franci Penov.

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

Permet de dire 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, 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 la même n-1 éléments dans le tableau et le seulement non appariés élément dans le 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 la XOR solution basée sur :)

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

Pour paraphraser François Penov de la solution.

L' (d'habitude) le problème est: é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).

Si vous savez que nous avons le nombre exact 1-1000, vous pouvez ajouter jusqu'les résultats et de les soustraire 500500 (sum(1, 1000)) du total. Cela donnera à la répétition de nombre, parce que sum(array) = sum(1, 1000) + repeated number.

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

Explication sur pourquoi il fonctionne, c'est dans @Matthieu M. de réponse.

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;
}

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);

Un triangle T(n) est la somme de n nombres naturels de 1 à n. Il peut être représenté comme n(n+1)/2. Ainsi, sachant que parmi donnée 1001 nombres naturels, un et un seul nombre est dupliqué, vous pouvez facilement somme de 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 de belles méthode de la découverte de cet T(n), sur la base de la base-10 représentation:

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

Amélioration de Fraci de la réponse repose sur la propriété de XORing valeurs consécutives:

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) définie comme (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 dans la forme canonique de f(n) est:

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

Dans le aux version, vous devez d'abord définir toutes les valeurs -1 et que vous parcourez vérifier si vous avez déjà inséré la valeur de l'auxiliaire de tableau. Si non (la valeur doit être -1, alors), insérer. Si vous avez un doublon, voici votre solution!

Dans celui sans aux, vous pouvez récupérer un élément de la liste et de vérifier si le reste de la liste contient cette valeur. Si il contient, ici, vous l'avez trouvé.

private static int findDuplicated(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    int[] checker = new int[array.length];
    Arrays.fill(checker, -1);
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        int checked = checker[value];
        if (checked == -1) {
            checker[value] = value;
        } else {
            return value;
        }
    }
    return -1;
}

private static int findDuplicatedWithoutAux(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        for (int j = i + 1; j < array.length; j++) {
            int toCompare = array[j];
            if (value == toCompare) {
                return array[i];
            }
        }
    }
    return -1;
}