Trouver des éléments manquants dans un tableau

Si vous avez un tableau A [1..n] de taille n, il contient des éléments de l’ensemble {1..n}. Cependant, deux des éléments sont manquants (et peut-être deux des éléments du tableau sont répétés). Trouvez les éléments manquants.

Par exemple, si n = 5, A peut être A [5] = {1,2,1,3,2}; et ainsi les éléments manquants sont {4,5}

L’approche que j’ai utilisée était:

int flag[n] = {0}; int i; for(i = 0; i < n; i++) { flag[A[i]-1] = 1; } for(i = 0; i < n; i++) { if(!flag[i]) { printf("missing: %d", (i+1)); } 

la complexité de l’espace vient à O (n). Je pense que c’est un code très kiddish et inefficace. Alors, pourriez-vous s’il vous plaît fournir un meilleur algo avec une meilleure complexité spatiale et temporelle

Théoriquement,

Il est possible de faire en espace O (1) (dans le modèle RAM, c’est-à-dire des mots O (1)) et en temps O (n) même avec un tableau en lecture seule.

Attention: Long post avec quelques mathématiques. Si vous êtes uniquement intéressé par le code et non par l’algorithme / la preuve, passez à la section de code. Cependant, vous aurez besoin de lire certaines parties de la section algorithme pour comprendre le code.


Algorithme

Supposons que les nombres manquants sont x et y.

Il y a deux possibilités pour le tableau:

1) Un numéro est répété trois fois et les nombres restants dans le tableau apparaissent exactement une fois.

Dans ce cas, l’astuce XOR avec seau fonctionnera.

Faites un XOR de tous les éléments du tableau avec 1,2, …, n.

Vous vous retrouvez avec z = x XOR y.

Il y a au moins un bit de z qui est non nul.

Maintenant, en différenciant les éléments du tableau en fonction de ce bit (deux compartiments), un XOR passe à nouveau dans le tableau.

Vous allez vous retrouver avec x et y.

Une fois que vous avez le x et le y, vous pouvez confirmer si ce sont bien les éléments manquants.

S’il se trouve que l’étape de confirmation échoue, alors nous devons avoir le deuxième cas:

2) Deux éléments répétés exactement deux fois et le rest apparaissant exactement une fois.

Laissez les deux éléments répétés être a et b (x et y sont les éléments manquants).

Attention: Maths à venir.

Soit S_k = 1^k + 2^k + .. + n^k

Par exemple S_1 = n(n+1)/2 , S_2 = n(n+1)(2n+1)/6 etc.

Maintenant, nous calculons sept choses:

 T_1 = Sum of the elements of the array = S_1 + a + b - x - y. T_2 = Sum of the squares = S_2 + a^2 + b^2 - x^2 - y^2 T_3 = Sum of cubes = S_3 + a^3 + b^3 - x^3 - y^3 T_4 = Sum of fourth powers = S_4 + a^4 + b^4 - x^4 - y^4 ... T_7 = Sum of seventh powers = S_7 + a^7 + b^7 - x^7 - y^7 

Notez que nous pouvons utiliser O (1) mots (au lieu de un) pour traiter les problèmes de débordement. (Je pense que 8 à 10 mots suffiront).

Soit Ci = T_i - S_i

Supposons maintenant que a, b, x, y sont les racines du polynôme du 4ème degré P(z) = z^4 + pz^3 + qz^2 + rz + s

Maintenant, nous essayons de transformer les sept équations ci-dessus en quatre équations linéaires dans p,q,r,s .

Par exemple, si nous faisons 4th Eqn + p * 3rd Eqn + q* 2nd equation + r* 1st equation

on a

C4 + p*C3 + q*C2 + r*C1 = 0

De même nous obtenons

 C5 + p*C4 + q*C3 + r*C2 + s*C1 = 0 C6 + p*C5 + q*C4 + r*C3 + s*C2 = 0 C7 + p*C6 + q*C5 + r*C4 + s*C3 = 0 

Ce sont quatre équations linéaires dans p,q,r,s qui peuvent être résolues par des techniques d’algèbre linéaire telles que l’élimination gaussienne.

Notez que p,q,r,s seront des rationnels et ne peuvent donc être calculés qu’avec une arithmétique entière.

Supposons maintenant qu’une solution p,q,r,s soit donnée à l’ensemble d’équations ci-dessus.

Considérons P(z) = z^4 + pz^3 + qz^2 + rz + s .

Ce que disent les équations ci-dessus est fondamentalement

 P(a) + P(b) - P(x) - P(y) = 0 aP(a) + bP(b) - xP(x) -yP(y) = 0 a^2 P(a) + b^2 P(b) - x^2 P(x) - y^2 P(y) = 0 a^3 P(a) + b^3 P(b) - x^3 P(x) - y^3 P(y) = 0 

Maintenant la masortingce

  1 1 -1 -1 ab -x -y a^2 b^2 -x^2 -y^2 a^3 b^3 -x^3 -y^3 

a le même déterminant que la masortingce de Vandermonde et est donc inversible si a,b,x,y sont distincts.

Il faut donc que P(a) = P(b) = P(x) = P(y) = 0 .

Maintenant, vérifiez quelles sont les racines de 1,2,3,...,n sont x^4 + px^3 + qx^2 + rx + s = 0 .

Il s’agit donc d’un algorithme d’espace linéaire en constante de temps.


Code

J’ai écrit le code C # (.Net 4.0) suivant et il semble fonctionner pour les quelques échantillons que j’ai essayés … (Remarque: je n’ai pas pris la peine de m’occuper du cas 1 ci-dessus).

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; namespace SOManaged { class Program { static void Main(ssortingng[] args) { ulong[] inp = {1,3,2,1,2}; ulong[] inp1 = { 1,2,3,4,5,6,7,8, 9,10,11,13,14,15, 16,17,18,19,20,21,5,14}; int N = 100000; ulong[] inp2 = new ulong[N]; for (ulong i = 0; i < (ulong)N; i++) { inp2[i] = i+1; } inp2[122] = 44; inp2[419] = 13; FindMissingAndRepeated(inp); FindMissingAndRepeated(inp1); FindMissingAndRepeated(inp2); } static void FindMissingAndRepeated(ulong [] nums) { BigInteger[] C = new BigInteger[8]; // Compute the C_i for (int k = 0; k < 8; k++) { C[k] = 0; } BigInteger i = 1; BigInteger n = 0; for (int j = 0; j < nums.Length; j++) { n = nums[j]; i = j + 1; for (int k = 1; k < 8; k++) { C[k] += i - n; n = n * nums[j]; i = i * (j + 1); } } for (int k = 1; k <= 7; k++) { Console.Write("C[" + k.ToString() + "] = " + C[k].ToString() +", "); } Console.WriteLine(); // Solve for p,q,r,s BigInteger[] pqrs = new BigInteger[4]; BigInteger[] constants = new BigInteger[4]; BigInteger[,] matrix = new BigInteger[4, 4]; int start = 4; for (int row = 0; row < 4; row++ ) { constants[row] = -C[start]; int k = start-1; for (int col = 0; col < 4; col++) { matrix[row, col] = C[k]; k--; } start++; } Solve(pqrs, matrix, constants, 4); for (int k = 0; k < 4; k++) { Console.Write("pqrs[" + k.ToString() + "] = " + pqrs[k].ToString() + ", "); } Console.WriteLine(); // Find the roots. for (int k = 1; k <= nums.Length; k++) { BigInteger x = new BigInteger(k); BigInteger p_k = x * x * x* x + pqrs[0] * x* x * x + pqrs[1] * x * x + pqrs[2] * x + pqrs[3]; if (p_k == 0) { Console.WriteLine("Found: " + k.ToString()); } } } // Solve using Cramer's method. // matrix * pqrs = constants. static void Solve(BigInteger[] pqrs, BigInteger[,] matrix, BigInteger[] constants, int n) { BigInteger determinant = Determinant(matrix, n); for (int i = 0; i < n; i++) { BigInteger[,] numerator = Replace(matrix, constants, n, i); BigInteger numDet = Determinant(numerator,4); pqrs[i] = numDet/ determinant; } } // Replace a column of matrix with constants. static BigInteger[,] Replace(BigInteger[,] matrix, BigInteger[] constants, int n, int col) { BigInteger[,] newMatrix = new BigInteger[n, n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j != col) { newMatrix[i, j] = matrix[i, j]; } else { newMatrix[i, j] = constants[i]; } } } return newMatrix; } // Recursively compute determinant for matrix. static BigInteger Determinant(BigInteger[,] matrix, int n) { BigInteger determinant = new BigInteger(0); int multiplier = 1; if (n == 1) { return matrix[0,0]; } for (int i = 0; i < n; i++) { BigInteger [,] subMatrix = new BigInteger[n-1,n-1]; int row = 0; for (int j=1; j < n; j++) { int col = 0; for (int k = 0; k < n ; k++) { if (k == i) { continue; } subMatrix[row,col] = matrix[j,k]; col++; } row++; } BigInteger subDeterminant = Determinant(subMatrix, n - 1); determinant += multiplier * subDeterminant * matrix[0,i]; multiplier = -multiplier; } return determinant; } } } 

La sortie est

 C[1] = 6, C[2] = 36, C[3] = 180, C[4] = 864, C[5] = 4116, C[6] = 19656, C[7] = 9 4380, pqrs[0] = -12, pqrs[1] = 49, pqrs[2] = -78, pqrs[3] = 40, Found: 1 Found: 2 Found: 4 Found: 5 C[1] = 15, C[2] = 407, C[3] = 9507, C[4] = 215951, C[5] = 4861515, C[6] = 108820 727, C[7] = 2424698067, pqrs[0] = -53, pqrs[1] = 980, pqrs[2] = -7396, pqrs[3] = 18480, Found: 5 Found: 12 Found: 14 Found: 22 C[1] = 486, C[2] = 189424, C[3] = 75861486, C[4] = 31342069984, C[5] = 130971109 69326, C[6] = 5492487308851024, C[7] = 2305818940736419566, pqrs[0] = -600, pqrs[1] = 83183, pqrs[2] = -3255216, pqrs[3] = 29549520, Found: 13 Found: 44 Found: 123 Found: 420 

Comme @j_random_hacker l’a fait remarquer, cela ressemble beaucoup à la recherche de doublons dans le temps O (n) et l’espace O (1) , et une adaptation de ma réponse ici fonctionne également. En pseudo-code:

 for i := 1 to n while A[A[i]] != A[i] swap(A[i], A[A[i]]) end if end for for i := 1 to n if A[i] != i then print i end if end for 

La première boucle permute le tableau de sorte que si l’élément x est présent au moins une fois, l’une de ces entrées sera à la position A[x] .

Notez que, bien qu’elle ait une boucle nestede, elle fonctionne toujours dans le temps O(N) – un échange n’est effectué que s’il existe un i tel que A[i] != i , et chaque échange définit au moins un élément tel que A[i] == i , là où ce n’était pas vrai auparavant. Cela signifie que le nombre total de swaps (et donc le nombre total d’exécutions du corps de la boucle while) est au plus N-1 .

Votre solution n’est pas mauvaise. Voici une alternative – Triez la liste et parcourez-la en vérifiant les nombres adjacents. Quand il y a un espace, imprimez tous les nombres entre les deux. Si k est la longueur du tableau et n le nombre à compter, on obtient O (k lg k + n) temps, O (1) espace

C’est un peu qwirky Comme tous vos chiffres sont positifs (par problème). Je ferai en sorte que le nombre à la position i-1 soit négatif si i est présent dans le tableau.

 int i; for(i = 0; i < n; i++) { A[abs(A[i])-1] = -1*abs(A[abs(A[i])-1]); } for(i = 0; i < n; i++) { if(A[i]>0) { printf("missing: %d", i+1); } 

Complexité O (n), pas d’utilisateur du tableau auxiliaire, mais détruit le tableau d’entrée.

Vous trouverez ci-dessous l’une des méthodes permettant d’identifier tous les nombres manquants lorsqu’un groupe ne contient que des nombres compris entre 1 et n inclus, sans utiliser d’espace supplémentaire. La complexité temporelle est O (n).

Prenons le plus petit nombre k tel qu’il n’est pas supposé être dans un tableau, donc k = n + 1 (appelons-le facteur d’addition).

première boucle à travers chaque tableau et pour chaque a [i] nous mettrons à jour un [a [i] – 1] + = k; après cette boucle, chaque élément du tableau contient deux ensembles d’informations, le nombre qui figurait à l’origine dans l’élément du tableau + k * (nombre d’occurrences de son numéro dans le tableau).

dans la seconde boucle, vous pouvez connaître le nombre de répétitions de ce nombre en effectuant une division entière du nombre à chaque emplacement par k. Et le numéro original à son emplacement serait un [i]% k;

Permet de travailler à travers un exemple

A[5] = {1,2,1,3,2};

ici (addfactor) k = 5 (longueur du tableau) + 1 = 6

Après la première boucle, le tableau ressemblerait si, si l’élément d’origine est m et que les occurrences de son numéro sont O(i) élément de tableau résultant serait m + k * O(i) cet élément diviser (entier) par k elemnent, et% k vous obtiendrez le tableau original.

A = {1 + 6*2, 2 + 6*2, 1 + 6*1, 3+6*0 , 2+6*0 }
A = {13, 14, 7, 3, 2 }

Voici le code C # qui (désolé, mon C est un peu rouillé, cela fait un moment.) Pourrait être transféré dans n’importe quelle langue simplement en remplaçant Printf & scanfs.

  static void Main(ssortingng[] args) { int[] A = { 1, 2, 1, 3, 2 }; PrintDuplicateAndMissing(A); Console.ReadLine(); } static void PrintDuplicateAndMissing(int[] array) { int addfactor = array.Length + 1; for (int i = 0; i < array.Length; i++) { array[array[i] - 1] += addfactor; // -1 only if array contains from 1 to n. if it is 0 to n (this -1 is not required) } for (int i = 0; i < array.Length; i++) { if ( (array[i] / addfactor) == 0 ) Console.WriteLine(string.Format("{0} is missing", i + 1)); // i + 1 only if array is 1 to n, if 0 to n then +1 is not required array[i] %= addfactor; //restore original content of the array } } 

Cycle chaque élément 0 … n-1.

 x = abs(A[i]) (with i = 0...n-1); A[x - 1] can be: > 0: we haven't checked the element, change its sign to negative: A[x - 1] = -A[x - 1] < 0: we already found the same number 

À la fin du cycle, passez chaque A [0 ... n-1]. L'indice des éléments positifs + 1 correspond aux nombres manquants.

Donc si

 y = abs(A[i]) > 0: i + 1 is missing. 

En C #

 var arr = new[] { 1, 2, 1, 2, 4 }; for (int i = 0; i < arr.Length; i++) { int x = Math.Abs(arr[i]); int y = arr[x - 1]; if (y > 0) { arr[x - 1] = -arr[x - 1]; } } for (int i = 0; i < arr.Length; i++) { int x = arr[i]; if (x > 0) { Console.WriteLine("Missing {0}", i + 1); } else { arr[i] = -arr[i]; } } 

Et le tableau est comme neuf.

Comme nous le soaps, nous recherchons des éléments compris entre 1 et N Créez un ensemble de hachage contenant 1 à N.

 foreach(int i in input) { if(hashset.contains(i)) { hashset.delete(i); } } return "remaining elements in Hashset."; 

Les éléments restants dans Hashset sont les éléments manquants.

As you have given an array of n size and find the missing number when it's in a sequence.

 #include main() { print("value of n"); scan("%d",&n); print("enter the elements"); for(i=0;i 

It would find the missing when its in sequence only.

Un extrait de code permettant de rechercher les éléments manquants sans sortinger le tableau ci-dessous:

  public static void series(int[] arr) { for (int i = 0; i < arr.length; i++) { while (arr[i] != i + 1) { int jump = arr[arr[i] - 1]; if (jump == arr[i]) { break; } arr[arr[i] - 1] = arr[i]; arr[i] = jump; } } System.out.println("Missing number is "); for (int i = 0; i < arr.length; i++) { if (arr[i] != i + 1) { System.out.println(i + 1); } else { arr[i] = -1; } } 

Ce code fonctionne pour une série de nombres de 0 à N.