Esempi di problemi usando hash table

8.1 Problema di trovare duplicati in un array

Problema: Dato un array di numeri. È necessario trovare e restituire tutti i duplicati nell'array.

Soluzione: Usiamo una hash table per tracciare i numeri già incontrati. Se un numero si ripete, lo aggiungiamo alla lista dei duplicati.

Esempio di implementazione:

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

# Esempi d'uso
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: []

Spiegazione:

• Creiamo un set vuoto seen per tracciare i numeri unici.
• Iteriamo su ogni elemento dell'array. Se l'elemento è già in seen, lo aggiungiamo alla lista duplicates.
• Se l'elemento non si trova in seen, lo aggiungiamo lì.
• Restituiamo la lista dei duplicati.

Nota che la funzione funziona correttamente con un array vuoto e con un array senza duplicati, restituendo un elenco vuoto in entrambi i casi.

8.2 Problema di verifica degli anagrammi

Problema: Date due stringhe. È necessario determinare se sono anagrammi (contengono gli stessi caratteri nello stesso numero).

Soluzione: Usiamo una hash table per contare la frequenza dei caratteri in entrambe le stringhe e confrontiamo i risultati.

Esempio di implementazione:

def are_anagrams(str1, str2):
    # Converting strings to lowercase to handle case sensitivity
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Counting character frequency in the first string
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Subtracting character frequency from the second string
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Checking that all values in the dictionary are zero
    return all(count == 0 for count in char_count.values())

# Esempi d'uso
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

Spiegazione:

• Se le lunghezze delle stringhe non coincidono, non possono essere anagrammi.
• Usiamo il dizionario char_count per contare la frequenza dei caratteri nella prima stringa.
• Iteriamo sulla seconda stringa e sottraiamo la frequenza dei caratteri.
• Verifichiamo che tutti i valori nel dizionario siano zero. Se è così, le stringhe sono anagrammi.

Nota che la funzione considera la sensibilità al maiuscolo/minuscolo, convertendo entrambe le stringhe in minuscolo prima del confronto. Elabora anche correttamente le stringhe vuote, considerandole anagrammi l'una dell'altra.

8.3 Problema di trovare coppie con una somma specifica

Problema: Dato un array di numeri e un valore di somma target. È necessario trovare tutte le coppie di numeri che sommano il valore target.

Soluzione: Usiamo una hash table per memorizzare i numeri e verificare se formano una coppia con il numero corrente che dà la somma target.

Esempio di implementazione:

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

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

Spiegazione:

• Creiamo un set vuoto seen per tracciare i numeri.
• Per ogni numero nell'array, calcoliamo il suo complemento complement (la differenza tra la somma target e il numero corrente).
• Se il complemento è già in seen, aggiungiamo la coppia (complement, num) alla lista pairs.
• Aggiungiamo il numero corrente a seen.
• Restituiamo la lista delle coppie.

È importante notare che questo algoritmo ha una complessità temporale O(n), dove n è il numero di elementi nell'array. Questo è significativamente più efficiente della soluzione ingenua con un doppio ciclo, che ha una complessità O(n^2). Utilizzare una hash table ci permette di trovare tutte le coppie con un solo passaggio sull'array, il che è particolarmente importante quando si lavora con grandi volumi di dati.

Per confronto, ecco come apparirebbe la soluzione ingenua con una complessità temporale 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

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

Come si può vedere, la soluzione ingenua richiede due cicli annidati, il che la rende inefficace per array grandi. La soluzione utilizzando una hash table permette di raggiungere lo stesso obiettivo molto più velocemente.