Supprimer les doublons sur place

Étant donné un tableau trié, conservez une copie de chaque valeur sans utiliser de tableau supplémentaire. Le traitement sur place économise de la mémoire et constitue une question classique en entretien. 🧹

Lorsque le tableau est trié, chaque doublon se trouve juste à côté de son autre occurrence. Vous ne comparez donc que des voisins, jamais le tableau entier.

Utilisez un pointeur lent qui indique la dernière valeur conservée et un pointeur rapide qui parcourt la suite à la recherche d’une nouvelle valeur.

Considérez slow comme la position d’écriture : tout ce qui se trouve à cette position ou avant est déjà nettoyé et unique.

Le pointeur fast se contente de lire vers l’avant. Il prend de l’avance et ne signale quelque chose à slow que lorsqu’il trouve une valeur qui n’a pas encore été conservée.

Si a[fast] est égal à a[slow], il s’agit d’une répétition : n’effectuez aucune action, à part avancer fast. Le doublon est ainsi ignoré discrètement.

Lorsque a[fast] est différent, avancez slow et copiez-y la nouvelle valeur. Cela remplace les anciens doublons par des données uniques récentes.

Après le parcours, slow + 1 correspond au nombre de valeurs uniques, toutes regroupées au début du tableau.

Tout ce qui se trouve après le préfixe unique est une donnée résiduelle sans importance. Le problème ne concerne que les slow + 1 premiers éléments : laissez donc le reste tel quel.

Un tableau vide contient zéro valeur unique. Gérez le cas n == 0 avant de commencer afin de ne pas lire au-delà de la fin.

Ce modèle lent-rapide s’exécute en temps O(n) et utilise O(1) espace supplémentaire, ce qui correspond exactement aux limites de mémoire strictes.

Vous supprimez des doublons sur place dans un tableau trié avec des pointeurs lent et rapide.

Dans un tableau trié, une paire de pointeurs lent-rapide supprime les doublons en un seul parcours en O(n), sans espace supplémentaire, et renvoie slow + 1 comme nombre de valeurs uniques. 🎉