Supprimez les Duplicatas d’un Tableau Trié : Question de Codage en Entretien en Python

Introduction

Lors des entretiens techniques, les questions de codage jouent un rôle crucial pour évaluer les compétences en algorithmes et en résolution de problèmes des candidats. Un problème classique fréquemment posé est celui de la suppression des duplicatas d’un tableau trié. Cet article vise à fournir une approche claire et pratique pour résoudre ce problème en Python, afin de vous préparer efficacement pour vos prochains entretiens.

Comprendre le Problème

Le problème ici est de retirer les duplicatas d’un tableau trié. Dans un tableau trié, un duplicata est une valeur qui se répète consécutivement. Par exemple, dans le tableau [1, 1, 2, 2, 3], les valeurs 1 et 2 apparaissent deux fois. L’objectif est de transformer ce tableau en [1, 2, 3], en éliminant les répétitions tout en conservant l’ordre trié.

Approches pour Résoudre le Problème

Approche Naïve

L’approche naïve consiste à créer une nouvelle liste pour stocker les éléments uniques rencontrés dans le tableau. Pour chaque élément du tableau, on vérifie s’il n’est pas déjà dans la liste temporaire et, s’il n’y est pas, on l’ajoute.

Complexité

• Temporelle: O(n), car nous devons parcourir chaque élément.
• Spatiale: O(n), en raison de l’utilisation d’une liste supplémentaire.

Limitations

Cette méthode n’est pas optimale en termes d’espace car elle utilise un espace de stockage supplémentaire.

Approche Optimisée avec In-Place Modification

L’approche plus efficace utilise la modification in-place, réduisant l’utilisation de mémoire supplémentaire. Elle emploie l’algorithme des deux pointeurs :

1. Initialisation: Définissez un slow (lent) et un fast (rapide) pointeur. Tous deux commencent au début du tableau.
2. Itération:
3. Si l’élément sous fast n’est pas un duplicata de celui sous slow, déplacez slow un pas en avant et updatez l’élément sous slow avec celui sous fast.
4. Avancez fast à travers tout le tableau.
5. Les éléments après slow ne comptent plus puisque ce sont des duplicatas.

Avantages

• Efficacité Spatiale: Modifie le tableau directement sans utiliser d’espace supplémentaire.
• Performance: Conserve une complexité temporelle de O(n).

Exemple de Code

def remove_duplicates(nums):
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# Exemple d'utilisation
nums = [1, 1, 2, 2, 3]
length = remove_duplicates(nums)
print(nums[:length])  # Output: [1, 2, 3]

Utilisation des Structures de Données Avancées

Une approche alternative consiste à utiliser un ensemble (set) pour stocker les éléments rencontrés. L’ensemble n’autorise pas les duplicatas, donc il les élimine automatiquement lors de l’ajout.

Comparaison

Cette méthode utilise plus de mémoire que l’approche des deux pointeurs, surtout lorsque l’on ne travaille pas in-place.

Implémentation en Python

Voici un exemple d’implémentation de la méthode optimisée en Python, avec des explications:

def remove_duplicates(nums):
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1  # Avance le pointeur `slow`
            nums[slow] = nums[fast]  # Met à jour la position `slow` avec la valeur unique trouvée

    return slow + 1  # La nouvelle longueur est `slow + 1`

# Test
nums = [1, 1, 2, 2, 3]
length = remove_duplicates(nums)
print(nums[:length])  # Devrait afficher [1, 2, 3]

Analyse de la Complexité

• Complexité Temporelle: O(n), car chaque élément est parcouru une fois.
• Complexité Spatiale: O(1), car la solution modifie le tableau directement.

L’approche in-place est plus économe en mémoire par rapport à d’autres qui utilisent des structures de données supplémentaires.

Cas Particuliers et Erreurs Courantes

• Tableaux sans duplicatas: Le code gère cela correctement en préservant la structure initiale.
• Tableaux petits ou vides: Vérifiez en amont pour éviter les erreurs d’accès aux index.
• Erreurs fréquentes: Mauvaise gestion des index, oublis de vérifications de base, comme tester si le tableau est vide.

Pratiques Recommandées pour les Entrevues

• Expliquer le raisonnement: Décrivez votre stratégie et pourquoi vous choisissez certaines approches.
• Tests et validation: Montrez votre code avec des tests simples pour prouver son efficacité.
• Trade-offs: Discutez des avantages et inconvénients des différentes méthodes pour montrer votre compréhension approfondie.

Conclusion

Nous avons exploré plusieurs solutions pour supprimer les duplicatas d’un tableau trié, en mettant l’accent sur une approche in-place efficace. Maîtriser cette technique est essentiel pour se distinguer dans les entretiens techniques. Nous vous encourageons à vous exercer régulièrement et à explorer d’autres problèmes pour enrichir vos compétences Python.

Ressources Supplémentaires

• Python Coding Tips: Remove Duplicates
• LeetCode: Remove Duplicates from Sorted Array
• Livres recommandés: « Cracking the Coding Interview » par Gayle Laakmann McDowell, « Effective Python » par Brett Slatkin.

En vous préparant avec ces ressources, vous serez bien armé pour affronter les défis des entretiens techniques. Bonne chance !