Przykłady zadań z użyciem tablic haszujących

8.1 Zadanie na znalezienie duplikatów w tablicy

Zadanie: Dana jest tablica liczb. Trzeba znaleźć i zwrócić wszystkie duplikaty w tablicy.

Rozwiązanie: Używamy tablicy haszującej do śledzenia liczb, które się już pojawiły. Jeśli liczba pojawia się ponownie, dodajemy ją do listy duplikatów.

Przykład implementacji:

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

# Przykłady użycia
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Wyjście: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Wyjście: []

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

Wyjaśnienie:

• Tworzymy pusty zestaw seen do śledzenia unikalnych liczb.
• Przechodzimy przez każdy element tablicy. Jeśli element jest już w seen, dodajemy go do listy duplicates.
• Jeśli element nie jest w seen, dodajemy go tam.
• Zwracamy listę duplikatów.

Zwróć uwagę, że funkcja działa poprawnie z pustą tablicą i z tablicą bez duplikatów, zwracając pustą listę w obu przypadkach.

8.2 Zadanie na sprawdzenie anagramów

Zadanie: Dane są dwa ciągi znaków. Trzeba ustalić, czy są anagramami (zawierają te same znaki w tej samej ilości).

Rozwiązanie: Używamy tablicy haszującej do zliczania częstotliwości znaków w obu ciągach i porównujemy wyniki.

Przykład implementacji:

def are_anagrams(str1, str2):
    # Przekształcamy ciągi na małe litery, aby uwzględnić różne przypadki liter
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Zliczanie częstotliwości znaków w pierwszym ciągu
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Odejmowanie częstotliwości znaków w drugim ciągu
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Sprawdzenie, czy wszystkie wartości w słowniku są równe 0
    return all(count == 0 for count in char_count.values())

# Przykłady użycia
print(are_anagrams("listen", "silent"))  # Wyjście: True
print(are_anagrams("hello", "world"))  # Wyjście: False
print(are_anagrams("", ""))  # Wyjście: True
print(are_anagrams("Tea", "Eat"))  # Wyjście: True

Wyjaśnienie:

• Jeśli długości ciągów nie są takie same, nie mogą być anagramami.
• Używamy słownika char_count do zliczania częstotliwości znaków w pierwszym ciągu.
• Przechodzimy przez drugi ciąg i odejmujemy częstotliwość znaków.
• Sprawdzamy, czy wszystkie wartości w słowniku są równe zeru. Jeśli tak, ciągi są anagramami.

Zwróć uwagę, że funkcja uwzględnia wielkość liter, przekształcając oba ciągi na małe litery przed porównaniem. Również poprawnie obsługuje puste ciągi, uznając je za anagramy siebie nawzajem.

8.3 Zadanie na znalezienie par z daną sumą

Zadanie: Dana jest tablica liczb i docelowa wartość sumy. Trzeba znaleźć wszystkie pary liczb, które w sumie dają wartość docelową.

Rozwiązanie: Używamy tablicy haszującej do przechowywania liczb i sprawdzania, czy tworzą parę z bieżącą liczbą, która daje docelową sumę.

Przykład implementacji:

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

# Przykład użycia
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Wyjście: [(1, 5), (1, 5)]

Wyjaśnienie:

• Tworzymy pusty zestaw seen do śledzenia liczb.
• Dla każdej liczby w tablicy obliczamy jej dopełnienie complement (różnicę między docelową sumą a bieżącą liczbą).
• Jeśli dopełnienie jest już w seen, dodajemy parę (complement, num) do listy pairs.
• Dodajemy bieżącą liczbę do seen.
• Zwracamy listę par.

Ważne jest, że ten algorytm ma złożoność czasową O(n), gdzie n to liczba elementów w tablicy. Jest to znacznie wydajniejsze niż naiwne rozwiązanie z podwójną pętlą, które ma złożoność O(n^2). Użycie tablicy haszującej pozwala nam znaleźć wszystkie pary w jednym przebiegu przez tablicę, co jest szczególnie ważne przy pracy z dużymi zbiorami danych.

Dla porównania, oto jak wyglądałoby naiwne rozwiązanie o złożoności czasowej 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

# Przykład użycia
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Wyjście: [(1, 5), (1, 5)]

Jak widać, naiwne rozwiązanie wymaga dwóch zagnieżdżonych pętli, co czyni je nieefektywnym dla dużych tablic. Rozwiązanie z użyciem tablicy haszującej pozwala osiągnąć ten sam cel znacznie szybciej.