Приклади задач з використанням хеш-таблиць

8.1 Завдання на пошук дублікатів у масиві

Завдання: Дано масив чисел. Потрібно знайти і повернути всі дублікати в масиві.

Рішення: Використовуємо хеш-таблицю для відстеження чисел, які вже зустрічались. Якщо число зустрічається повторно, додаємо його в список дублікатів.

Приклад реалізації:

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

# Приклади використання
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Вивід: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Вивід: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # Вивід: []

Пояснення:

• Створюємо порожню множину seen для відстеження унікальних чисел.
• Проходимо по кожному елементу масиву. Якщо елемент уже є в seen, додаємо його в список duplicates.
• Якщо елемент не знайдений в seen, додаємо його туди.
• Повертаємо список дублікатів.

Зверни увагу, що функція коректно працює з порожнім масивом і з масивом без дублікатів, повертаючи порожній список в обох випадках.

8.2 Завдання на перевірку анаграм

Завдання: Дано дві строки. Потрібно визначити, чи є вони анаграмами (містять ті ж самі символи в однаковій кількості).

Рішення: Використовуємо хеш-таблицю для підрахунку частоти символів в обох строках і порівнюємо результати.

Приклад реалізації:

def are_anagrams(str1, str2):
    # Приводимо строки до нижнього регістру для обліку різного регістру букв
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Підрахунок частоти символів у першій стрічці
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Віднімання частоти символів у другій стрічці
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Перевірка, що всі значення в словнику дорівнюють 0
    return all(count == 0 for count in char_count.values())

# Приклади використання
print(are_anagrams("listen", "silent"))  # Вивід: True
print(are_anagrams("hello", "world"))  # Вивід: False
print(are_anagrams("", ""))  # Вивід: True
print(are_anagrams("Tea", "Eat"))  # Вивід: True

Пояснення:

• Якщо довжини строк не співпадають, вони не можуть бути анаграмами.
• Використовуємо словник char_count для підрахунку частоти символів у першій стрічці.
• Проходимо по другій стрічці та віднімаємо частоту символів.
• Перевіряємо, що всі значення в словнику дорівнюють нулю. Якщо так, строки є анаграмами.

Зверни увагу, що функція враховує регістр букв, приводячи обидві строки до нижнього регістру перед порівнянням. Також вона коректно обробляє порожні строки, вважаючи їх анаграмами одна одної.

8.3 Завдання на знаходження пар із заданою сумою

Завдання: Дано масив чисел і цільове значення суми. Потрібно знайти всі пари чисел, які в сумі дають цільове значення.

Рішення: Використовуємо хеш-таблицю для зберігання чисел і перевірки, чи утворюють вони пару з поточним числом, яка дає цільову суму.

Приклад реалізації:

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

# Приклад використання
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Вивід: [(1, 5), (1, 5)]

Пояснення:

• Створюємо порожню множину seen для відстеження чисел.
• Для кожного числа у масиві обчислюємо його доповнення complement (різницю між цільовою сумою та поточним числом).
• Якщо доповнення вже є в seen, додаємо пару (complement, num) у список pairs.
• Додаємо поточне число в seen.
• Повертаємо список пар.

Важливо зазначити, що цей алгоритм має часову складність O(n), де n — кількість елементів у масиві. Це значно ефективніше наївного рішення з подвійним циклом, яке має складність O(n^2). Використання хеш-таблиці дозволяє нам знайти всі пари за один прохід по масиву, що особливо важливо при роботі з великими обсягами даних.

Для порівняння, ось як виглядало б наївне рішення з часовою складністю 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

# Приклад використання
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Вивід: [(1, 5), (1, 5)]

Як видно, наївне рішення вимагає двох вкладених циклів, що робить його неефективним для великих масивів. Рішення з використанням хеш-таблиці дозволяє досягти тієї ж мети набагато швидше.