Beispiele für Aufgaben mit Hash-Tabellen

8.1 Aufgabe zur Suche nach Duplikaten im Array

Aufgabe: Ein Array von Zahlen ist gegeben. Finde und gib alle Duplikate im Array zurück.

Lösung: Wir verwenden eine Hash-Tabelle, um die Zahlen, die bereits aufgetreten sind, zu verfolgen. Wenn eine Zahl erneut auftritt, fügen wir sie zur Liste der Duplikate hinzu.

Implementierungsbeispiel:

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

# Verwendungsmöglichkeiten
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Ausgabe: [2, 4]

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

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

Erklärung:

• Wir erstellen eine leere Menge seen zur Verfolgung der einzigartigen Zahlen.
• Wir durchlaufen jedes Element im Array. Wenn das Element bereits in seen ist, fügen wir es zur Liste duplicates hinzu.
• Wenn das Element nicht in seen gefunden wird, fügen wir es hinzu.
• Wir geben die Liste der Duplikate zurück.

Beachte, dass die Funktion korrekt mit einem leeren Array und einem Array ohne Duplikate funktioniert und in beiden Fällen eine leere Liste zurückgibt.

8.2 Aufgabe zur Überprüfung von Anagrammen

Aufgabe: Zwei Strings sind gegeben. Bestimme, ob sie Anagramme sind (die gleichen Zeichen in gleicher Anzahl enthalten).

Lösung: Wir verwenden eine Hash-Tabelle, um die Häufigkeit der Zeichen in beiden Strings zu zählen und vergleichen die Ergebnisse.

Implementierungsbeispiel:

def are_anagrams(str1, str2):
    # Wir setzen die Strings auf Kleinbuchstaben um unterschiedliche Großschreibung zu berücksichtigen
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Zählen der Zeichenhäufigkeit im ersten String
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Subtraktion der Zeichenhäufigkeit im zweiten String
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Überprüfung, dass alle Werte im Wörterbuch gleich 0 sind
    return all(count == 0 for count in char_count.values())

# Verwendungsmöglichkeiten
print(are_anagrams("listen", "silent"))  # Ausgabe: True
print(are_anagrams("hello", "world"))  # Ausgabe: False
print(are_anagrams("", ""))  # Ausgabe: True
print(are_anagrams("Tea", "Eat"))  # Ausgabe: True

Erklärung:

• Wenn die Längen der Strings nicht übereinstimmen, können sie keine Anagramme sein.
• Wir verwenden ein Wörterbuch char_count zur Zählung der Zeichenhäufigkeit im ersten String.
• Wir durchlaufen den zweiten String und subtrahieren die Zeichenhäufigkeit.
• Wir überprüfen, dass alle Werte im Wörterbuch gleich null sind. Wenn ja, sind die Strings Anagramme.

Beachte, dass die Funktion die Buchstabengroßschreibung berücksichtigt, indem beide Strings vor dem Vergleich in Kleinbuchstaben umgewandelt wurden. Außerdem behandelt sie leere Strings korrekt, indem sie sie als Anagramme voneinander betrachtet.

8.3 Aufgabe zum Finden von Paaren mit einer gegebenen Summe

Aufgabe: Ein Array von Zahlen und ein Zielwert der Summe sind gegeben. Finde alle Zahlenpaare, die zusammen den Zielwert ergeben.

Lösung: Wir verwenden eine Hash-Tabelle, um Zahlen zu speichern und zu überprüfen, ob sie mit der aktuellen Zahl ein Paar bilden, das die Zielsumme ergibt.

Implementierungsbeispiel:

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

# Beispielverwendung
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Ausgabe: [(1, 5), (1, 5)]

Erklärung:

• Wir erstellen eine leere Menge seen zur Verfolgung der Zahlen.
• Für jede Zahl im Array berechnen wir ihr Komplement complement (Differenz zwischen der Zielsumme und der aktuellen Zahl).
• Wenn das Komplement bereits in seen ist, fügen wir das Paar (complement, num) zur Liste pairs hinzu.
• Wir fügen die aktuelle Zahl zu seen hinzu.
• Wir geben die Liste der Paare zurück.

Wichtig zu beachten ist, dass dieser Algorithmus eine Zeitkomplexität von O(n) hat, wobei n die Anzahl der Elemente im Array ist. Das ist erheblich effizienter als die naive Lösung mit einer doppelten Schleife, die eine Komplexität von O(n^2) hat. Die Verwendung einer Hash-Tabelle ermöglicht es uns, alle Paare in einem Durchgang über das Array zu finden, was besonders wichtig ist, wenn mit großen Datenmengen gearbeitet wird.

Zum Vergleich, hier ist, wie die naive Lösung mit einer Zeitkomplexität von O(n^2) aussehen würde:

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

# Beispielverwendung
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Ausgabe: [(1, 5), (1, 5)]

Wie ersichtlich, erfordert die naive Lösung zwei verschachtelte Schleifen, was sie für große Arrays ineffizient macht. Mit der Hash-Tabellenlösung gelingt es, das gleiche Ziel viel schneller zu erreichen.