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.
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.
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é.
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).
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.
Remarques supplémentaires :
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!