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

Recherche de doublons dans le temps O(n) et l'espace O(1)

Étant donné un tableau de n éléments contenant des nombres de 0 à n -1, où certains nombres peuvent apparaître plusieurs fois, le but est de trouver les éléments en double en un temps O(n) et en utilisant un espace mémoire constant.

Pour y parvenir, nous pouvons utiliser une approche intrigante qui ne Ne nécessite pas de structures de données supplémentaires telles que des tables de hachage.

L'algorithme proposé fonctionne comme suit :

1. Boucle de permutation :

   • Parcourez le tableau pour i de 0 à n-1.
   • Dans cette boucle, effectuez les étapes suivantes jusqu'à ce que A[A[i]] soit égal à A[i]. Cela implique que l'élément A[i] est dans sa position correcte.
   • Échangez A[i] avec A[A[i]]. Cela rapproche efficacement l'élément A[i] de sa position correcte.

2. Boucle d'identification de duplication :

   • Parcourez à nouveau le tableau, de i de 0 à n-1.
   • Si A[i] n'est pas égal à i, cela signifie qu'il y a un double de i à l'index A[i].
   • Imprimez A[i] en double.

Cet algorithme garantit que tous les éléments en double sont identifiés. La boucle externe s'exécute n fois, tandis que la boucle interne s'exécute au plus n-1 fois. Par conséquent, l’algorithme s’exécute en temps O(n). Il n'utilise aucune structure de données supplémentaire, ce qui signifie qu'il fonctionne dans l'espace O(1).

Le code fourni illustre l'implémentation de l'algorithme en C .

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!