Hash-table istifadə edərək həllərin nümunələri

8.1 Massivdə təkrarları tapmaq tapşırığı

Tapşırıq: Verilən ədədlər massivindən bütün təkrarları tapmaq və geri qaytarmaq lazımdır.

Həll: Artıq rast gəlinmiş ədədləri izləmək üçün hash-table istifadə edəcəyik. Əgər ədəd yenidən rast gəlinirsə, onu təkrarların siyahısına əlavə edirik.

Reallaşdırma nümunəsi:

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

# İstifadə nümunələri
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Çıxış: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Çıxış: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # Çıxış: []

İzah:

• Unikal ədədləri izləmək üçün boş seen set yaradırıq.
• Massivin hər bir elementi üzrə dövr edirik. Əgər element artıq seen-də varsa, onu duplicates siyahısına əlavə edirik.
• Əgər element seen-də tapılmasa, onu seen-ə əlavə edirik.
• Təkrarların siyahısını geri qaytarırıq.

Qeyd edin ki, funksiya boş massiv və təkrarsız massiv üçün düzgün işləyir, hər iki halda boş siyahı qaytarır.

8.2 Anagramları yoxlamaq üçün məsələ

Məsələ: İki sətir verilib. Onların anagram olub-olmadığını (eyni simvolların eyni sayda olub-olmadığını) müəyyən etmək lazımdır.

Həll: Hash-tablosundan istifadə edərək hər iki sətirdə simvolların tezliyini sayır və nəticələri müqayisə edirik.

Reallaşdırma nümunəsi:

def are_anagrams(str1, str2):
    # Böyük-kiçik hərf fərqini nəzərə almamaq üçün sətirləri kiçik hərflərə çeviririk
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Birinci sətirdə simvolların tezliyini sayırıq
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # İkinci sətirdə simvolların tezliyini çıxırıq
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Lüğətdəki bütün dəyərlərin 0-a bərabər olduğunu yoxlayırıq
    return all(count == 0 for count in char_count.values())

# İstifadə nümunələri
print(are_anagrams("listen", "silent"))  # Çıxış: True
print(are_anagrams("hello", "world"))  # Çıxış: False
print(are_anagrams("", ""))  # Çıxış: True
print(are_anagrams("Tea", "Eat"))  # Çıxış: True

İzah:

• Əgər sətirlərin uzunluğu uyğun gəlmirsə, onlar anagram ola bilməzlər.
• Birinci sətirdə simvolların tezliyini saymaq üçün char_count lüğətindən istifadə edirik.
• İkinci sətirdən keçərək simvolların tezliyini azaldırıq.
• Lüğətdəki bütün dəyərlərin 0-a bərabər olduğunu yoxlayırıq. Əgər belədirsə, sətirlər anagramdır.

Diqqət yetirin ki, funksiya hərflərin registrini nəzərə alır, sətirləri müqayisədən əvvəl kiçik hərflərə çevirir. Həmçinin, o, boş sətirləri düzgün emal edir və onları bir-birinin anagramı kimi qəbul edir.

8.3 Verilmiş cəmi olan cütlərin tapılması üzrə tapşırıq

Tapşırıq: Rəqəmlərdən ibarət bir massiv və məqsəd cəmi verilmişdir. Cəmi məqsəd dəyərinə bərabər olan bütün rəqəm cütlərini tapmaq lazımdır.

Həll: Hash cədvəlindən istifadə edərək rəqəmləri saxlayacağıq və onların məqsəd cəm ilə uyğun cüt yaradır-yaratmadığını yoxlayacağıq.

Həllin nümunəsi:

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

# İstifadə nümunəsi
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Çıxış: [(1, 5), (1, 5)]

İzah:

• Rəqəmləri izləmək üçün boş bir seen çoxluğunu yaradırıq.
• Massivdəki hər bir rəqəm üçün onun tamamlayıcısını complement (məqsəd cəm ilə cari rəqəm arasındakı fərq) hesablayırıq.
• Əgər tamamlayıcı artıq seen çoxluğunda varsa, cüt (complement, num) siyahıya pairs əlavə edirik.
• Cari rəqəmi seen çoxluğuna əlavə edirik.
• Rəqəm cütləri siyahısını qaytarırıq.

Qeyd etmək vacibdir ki, bu alqoritmin vaxt mürəkkəbliyi O(n)-dir, burada n massivdəki elementlərin sayıdır. Bu, ikiqat döngü ilə olan sadə həllin O(n^2) mürəkkəbliyindən daha effektivdir. Hash cədvəlindən istifadə, massivdəki bütün cütləri bir keçiddə tapmaq imkanı verir ki, bu da böyük verilənlərdə işləyərkən xüsusilə əhəmiyyətlidir.

Müqayisə üçün, vaxt mürəkkəbliyi O(n^2) olan sadə həll belə görünərdi:

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

# İstifadə nümunəsi
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Çıxış: [(1, 5), (1, 5)]

Göründüyü kimi, sadə həll iki iç-içə döngü tələb edir, bu da böyük massivlər üçün qeyri-effektivdir. Hash cədvəlindən istifadə edən həll eyni məqsədə çox daha sürətli çatmağa imkan verir.