Trouver le nombre manquant dans un tableau

Question

Un tableau a[] contient tous les entiers de 0 à N, sauf un. Cependant, vous ne pouvez pas accéder à un élément avec une seule opération. Au lieu de cela, vous pouvez appeler get(i, k) qui renvoie le kième bit de a[i] ou vous pouvez appeler swap(i, j) qui échange les ième et jième éléments de a[] . Concevez un algorithme O(N) pour trouver le nombre entier manquant. (Pour simplifier, supposez que N est une puissance de 2).

Answer 1

Si N est une puissance de 2, cela peut être fait en O(N) en utilisant diviser pour mieux régner .

Notez qu'il existe logN des bits dans les chiffres. Maintenant, en utilisant cette information - vous pouvez utiliser une combinaison de algorithme de sélection basé sur la partition y radix-sort .

1. Interroger les nombres pour le premier bit, et diviser le tableau en deux. moitié - la première moitié a le bit 0, l'autre moitié a le bit 1. swap() pour le partitionnement de la matrice).
2. Notez qu'une moitié a ceil(N/2) et l'autre a floor(N/2) éléments.
3. Répétez le processus pour le plus petit tableau, jusqu'à ce que vous trouviez l'élément manquant. manquant.

La complexité de cette approche sera N + N/2 + N/4 + ... + 1 < 2N donc c'est O(n)

Answer 2

O(N*M), où M est le nombre de bits :

N est une puissance de 2, un seul numéro est manquant, donc si vous vérifiez chaque bit, et comptez les numéros où ce bit est 0, et comptez où est 1, vous obtiendrez 2^(M-1) et 2^(M-1)-1, le plus court appartient au numéro manquant. Avec cela, vous pouvez obtenir tous les bits du nombre manquant.

Answer 3

Il n'y a même pas besoin d'utiliser l'opération swap ! ! Utilisez XOR ! Ok, d'abord vous pouvez calculer le XOR binaire de tous les nombres de 0 à N. Donc d'abord :

long nxor = 0;
for (long i = 0; i <= N; i++)
    nxor = XOR(nxor, i);

Ensuite, nous pouvons calculer le XOR de tous les nombres dans le tableau, c'est aussi simple. Appelons K - le nombre maximal de bits dans tous les nombres.

long axor = 0;

long K = 0;
long H = N;
while (H > 0)
{
   H >>= 1; K++;
}

for (long i = 0; i < N - 1; i++)
   for (long j = 0; j < K; k++)
    axor = XOR(axor, get(i,j) << j);

Enfin, vous pouvez calculer le XOR du résultat :

long result = XOR(nxor, axor).

Et d'ailleurs, si n est une puissance de 2, alors la valeur de nxor sera égale à n ;-) !

Answer 4

Et aussi une autre réponse quand nous utiliserons l'opération somme au lieu de l'opération xor. Vous trouverez le code ci-dessous.

long allsum = n * (n + 1) / 2;
long sum = 0;

long K = 0;
long H = N;
while (H > 0)
{
   H >>= 1; K++;
}

for (long i = 0; i < N - 1; i++)
   for (long j = 0; j < K; k++)
    sum += get(i,j) << j;

long result = allsum - sum.

Answer 5

Supposons que l'entrée soit a[]=0,1,2,3,4,5,7,8 de sorte que 6 est manquant. Les chiffres sont triés par commodité uniquement, car il n'est pas nécessaire de les trier pour que la solution fonctionne.

Desde N es 8 alors les nombres sont représentés en utilisant 4 bits. Sur le site 0000 a 1000 .

Commencez par partitionner le tableau en utilisant le bit le plus significatif.

Vous obtenez 0,1,2,3,4,5,7 y 8 . Puisque 8 est présent, continuez avec la partition de gauche.

Partitionner le sous-réseau en utilisant le deuxième bit le plus significatif.

Vous obtenez 0,1,2,3 y 4,5,7 . Continuez maintenant avec la partition qui a un nombre impair d'éléments, c'est-à-dire 4,5,7 .

Partitionner le sous tableau en utilisant le 3ème bit le plus significatif.

Vous obtenez 4,5 y 7 . Continuez encore avec la partition qui a un nombre impair d'éléments, c'est-à-dire 7 .

Partitionner le sous-réseau en utilisant le 4ème bit le plus significatif, vous obtenez nothing y 7 .

Donc le nombre manquant est 6 .

Un autre exemple :

• a[]=0,1,3,4,5,6,7,8 de sorte que 2 est manquant.
• 1ère partition de bits : 0,1,3,4,5,6,7 y 8 , continuez avec 0,1,3,4,5,6,7 .
• 2ème partition de bits : 0,1,3 y 4,5,6,7 , continuez avec 0,1,3 (nombre impair d'éléments).
• 3ème partition de bits : 0,1 y 3 , continuez avec 3 (nombre impair d'éléments).
• 4ème bit de partition : nothing y 3 donc 2 est manquant.

Un autre exemple :

• a[]=1,2,3,4,5,6,7,8 de sorte que 0 est manquant.
• 1ère partition de bits : 1,2,3,4,5,6,7 y 8 , continuez avec 1,2,3,4,5,6,7 .
• 2ème partition de bits : 1,2,3 y 4,5,6,7 , continuez avec 1,2,3 (nombre impair d'éléments).
• 3ème partition de bits : 1 y 2,3 , continuez avec 1 (nombre impair d'éléments).
• 4ème bit de partition : nothing y 1 donc 0 est manquant.

La 1ère partition prend N opérations. La 2ème partition prend N opérations. La 3ème partition prend N/2 opérations. La 4ème partition prend N/4 des opérations. Et ainsi de suite.

Le temps d'exécution est donc de O(N+N+N/2+N/4+...)=O(N).