Comment rechercher des doublons dans un tableau avec un temps O(n) et un espace O(1) ?

Algorithme efficace pour trouver des doublons dans le temps O(n) et l'espace O(1)

Dans ce défi de programmation, nous recherchons un algorithme pour identifier et imprimer les éléments en double dans un tableau d'entiers allant de 0 à n-1, avec des répétitions possibles. Le défi nécessite un algorithme qui fonctionne dans une complexité temporelle O(n) et ne consomme qu'un espace mémoire constant.

Une approche efficace de ce problème est la technique de « modification de tableau ». L'algorithme fonctionne comme suit :

1. Première boucle :

   • Initialiser une boucle qui parcourt chaque élément du tableau, notée A[i].
   • Pour chaque A[i], déterminez si A[A[i]] est égal à A[i].
   • Sinon, échangez A[i] avec A[ A[i]].

2. Deuxième boucle :

   • Réinitialiser la boucle pour parcourir chaque A[i] encore une fois.
   • Pour tout A[i] qui n'est pas égal à i, imprimez A[i]. Cette étape identifie les éléments en double car tout élément non en double aura A[A[i]] égal à i (c'est-à-dire qu'il est dans sa position correcte).

Cet algorithme fonctionne en temps O(n) puisque chaque élément est vérifié et modifié au plus une fois dans la première boucle. De plus, comme aucune structure de données supplémentaire n'est utilisée, il utilise uniquement l'espace O(1).

Par exemple, considérons le tableau d'entrée {1, 2, 3, 1, 3, 0, 6}. Après avoir exécuté l'algorithme, le tableau est modifié comme suit :

[1, 2, 3, 1, 3, 0, 0]

La deuxième boucle imprime ensuite les éléments en double, 1 et 3.

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!