Comment pouvons-nous trouver des doublons dans un tableau de nombres de 0 à n-1 dans le temps O(n) et l'espace O(1) ?

Trouver des doublons dans le temps O(n) et l'espace O(1) : une explication approfondie

Le problème posé consiste à identifier les doublons éléments dans un tableau contenant des nombres allant de 0 à n-1. Le défi consiste à y parvenir efficacement, dans une complexité temporelle O(n) et en utilisant uniquement un espace mémoire constant (O(1)).

La solution présentée utilise une technique ingénieuse qui ne nécessite aucune table de hachage ni aucune autre donnée supplémentaire. structures. Au lieu de cela, il exploite les valeurs du tableau lui-même pour identifier et marquer les éléments en double.

1. Permutation du tableau :

   La boucle interne permute le tableau basé sur la logique suivante :

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   Cette étape de permutation garantit que si un élément x existe dans le tableau, au moins une de ses instances sera positionnée en A[x]. Ceci est crucial pour les étapes suivantes.

2. Identification des doublons :

   La boucle externe inspecte chaque élément A[i] :

   for i := 0 to n - 1
       if A[i] != i then
           print A[i]
       end if
   end for

   Si A[i] != i, cela signifie que i n'est pas présent à sa juste place dans le tableau. Par conséquent, il s'agit d'un élément en double, et il est imprimé.

3. Analyse de la complexité temporelle :

   La technique s'exécute en temps O(n) . La boucle imbriquée a une boucle externe qui itère n fois et une boucle interne qui effectue au plus n - 1 itérations (car chaque échange rapproche un élément de sa position correcte). Ainsi, le nombre total d'itérations est limité par n*(n - 1), qui est O(n^2), mais peut être simplifié en O(n) car n*(n - 1) = n^2 - n = n(n - 1) = n*n - n ≪ n*n = O(n^2) = O(n).

4. Analyse de la complexité spatiale :

   L'algorithme utilise uniquement un espace constant , indépendamment de la taille de l'entrée. L'idée clé est que l'espace utilisé pour les permutations est déjà présent dans le tableau d'entrée. Aucune structure de stockage supplémentaire n'est requise.

5. Remarques supplémentaires :

   • L'algorithme suppose que le tableau contient des entiers de 0 à n - 1.
   • La complexité temporelle reste la même, même en présence de doublons.
   • L'algorithme est efficace pour les tableaux de taille petite à moyenne. Pour les grands tableaux, des approches alternatives utilisant des structures de données telles que des tables de hachage peuvent être plus adaptées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!