Supprimer les doublons sur place
Utiliser une paire de pointeurs, l’un lent et l’autre rapide
Supprimer les doublons sur place est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
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. 🧹
Pourquoi le tri aide
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.
Deux rôles, deux pointeurs
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.
slow = 0
fast = 1Le pointeur lent écrit
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 rapide lit
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.
Ignorer les répétitions
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.
for fast in range(1, n):
if a[fast] == a[slow]:
continueTrouver une nouvelle valeur
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.
else:
slow += 1
a[slow] = a[fast]La réponse est la longueur
Après le parcours, slow + 1 correspond au nombre de valeurs uniques, toutes regroupées au début du tableau.
return slow + 1Ignorer la fin
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.
Ne pas oublier le tableau vide
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.
if n == 0:
return 0Un seul parcours, sans espace supplémentaire
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.
Vérification rapide
Vous supprimez des doublons sur place dans un tableau trié avec des pointeurs lent et rapide.
Récapitulatif
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. 🎉
Questions Fréquemment Posées
La leçon « Supprimer les doublons sur place » est-elle gratuite ?
Oui — le texte complet de « Supprimer les doublons sur place » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Supprimer les doublons sur place » ?
Utiliser une paire de pointeurs, l’un lent et l’autre rapide Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Supprimer les doublons sur place » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Deux pointeurs sur un tableau trié
- Trouver une paire d’une somme donnée
- Supprimer les doublons sur place
- Fusionner deux séquences triées