Exemples de problèmes utilisant des tables de hachage

8.1 Problème de recherche de doublons dans un tableau

Problème: Vous avez un tableau de nombres. Vous devez trouver et retourner tous les doublons dans le tableau.

Solution: Utilisons une table de hachage pour suivre les nombres déjà rencontrés. Si un nombre apparaît à nouveau, on l'ajoute à la liste des doublons.

Exemple d'implémentation :

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Exemples d'utilisation
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Output: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Output: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # Output: []

Explication :

• On crée un ensemble vide seen pour suivre les nombres uniques.
• On parcourt chaque élément du tableau. Si l'élément est déjà dans seen, on l'ajoute à la liste duplicates.
• Si l'élément n'est pas dans seen, on l'ajoute.
• On retourne la liste des doublons.

À noter que la fonction fonctionne correctement avec un tableau vide et un tableau sans doublons, retournant une liste vide dans les deux cas.

8.2 Problème de vérification d'anagrammes

Problème : Vous avez deux chaînes de caractères. Vous devez déterminer si elles sont des anagrammes (contiennent les mêmes caractères avec la même fréquence).

Solution: Utilisons une table de hachage pour compter la fréquence des caractères dans les deux chaînes et comparons les résultats.

Exemple d'implémentation :

def are_anagrams(str1, str2):
    # Convertir les chaînes en minuscules pour ignorer la casse
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Comptage de la fréquence des caractères dans la première chaîne
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Soustraction de la fréquence des caractères dans la deuxième chaîne
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Vérification que toutes les valeurs dans le dictionnaire sont nulles
    return all(count == 0 for count in char_count.values())

# Exemples d'utilisation
print(are_anagrams("listen", "silent"))  # Output: True
print(are_anagrams("hello", "world"))  # Output: False
print(are_anagrams("", ""))  # Output: True
print(are_anagrams("Tea", "Eat"))  # Output: True

Explication :

• Si les longueurs des chaînes ne correspondent pas, elles ne peuvent pas être des anagrammes.
• On utilise le dictionnaire char_count pour compter la fréquence des caractères dans la première chaîne.
• On parcourt la deuxième chaîne et soustrait la fréquence des caractères.
• On vérifie que toutes les valeurs dans le dictionnaire sont à zéro. Si c'est le cas, les chaînes sont des anagrammes.

Notez que la fonction tient compte de la casse en convertissant les chaînes en minuscules avant la comparaison. Elle traite également correctement les chaînes vides, les considérant comme des anagrammes l'une de l'autre.

8.3 Problème de trouvaille de paires avec une somme donnée

Problème : Vous avez un tableau de nombres et une valeur cible pour la somme. Vous devez trouver toutes les paires de nombres dont la somme est égale à la valeur cible.

Solution: Utilisons une table de hachage pour stocker les nombres et vérifier s'ils forment une paire avec le nombre actuel qui donne la somme cible.

Exemple d'implémentation :

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []
    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)
    return pairs

# Exemple d'utilisation
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Output: [(1, 5), (1, 5)]

Explication :

• On crée un ensemble vide seen pour suivre les nombres.
• Pour chaque nombre dans le tableau, on calcule son complément complement (différence entre la somme cible et le nombre actuel).
• Si le complément est déjà dans seen, on ajoute la paire (complement, num) à la liste pairs.
• On ajoute le nombre actuel à seen.
• On retourne la liste des paires.

Il est important de noter que cet algorithme a une complexité temporelle de O(n), où n est le nombre d'éléments dans le tableau. C'est nettement plus efficace que la solution naïve à double boucle, qui a une complexité de O(n^2). L'utilisation d'une table de hachage nous permet de trouver toutes les paires en un seul passage du tableau, ce qui est particulièrement important pour travailler avec de grands volumes de données.

Pour comparaison, voici à quoi ressemblerait la solution naïve avec une complexité temporelle de O(n^2) :

def find_pairs_naive(arr, target_sum):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# Exemple d'utilisation
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Output: [(1, 5), (1, 5)]

Comme vous pouvez le voir, la solution naïve nécessite deux boucles imbriquées, ce qui la rend inefficace pour les grands tableaux. La solution utilisant une table de hachage permet d'atteindre le même objectif beaucoup plus rapidement.