İki göstərici metodu

2.1 İki göstərici metodunun tərifi.

İki göstərici metodu — bu, massivlər və sətirlərlə bağlı müxtəlif tapşırıqları həll etmək üçün istifadə olunan bir texnikadır və burada müəyyən qaydalara görə məlumatlar üzərində hərəkət edən iki göstəricidən (indeksdən) istifadə olunur. Bu metod cüt elementlər, alt qruplar tapmaqla bağlı məsələləri və müəyyən şərtlərə cavab verənləri effektiv həll etməyə imkan verir.

Bu metod adətən məlumat quruluşunun əks uclarında iki göstəricidən istifadə etməyi və onları bir-birinə doğru və ya müəyyən bir qaydaya əsasən hərəkət etdirməyi nəzərdə tutur. İki göstərici metodu daha sadə yanaşmalarla müqayisədə algoritmin vaxt mürəkkəbliyini əhəmiyyətli dərəcədə azalda bilər.

Əsas prinsiplər

1. İki göstəricinin başlanğıc vəziyyəti: Göstəricilər massiv və ya sətirin əvvəlində və sonunda, yaxud tapşırığa uyğun olaraq müxtəlif indekslərdə quraşdırıla bilər.
2. Göstəricilərin hərəkəti: Göstəricilər müəyyən bir qaydaya uyğun hərəkət edir (məsələn, hər iki göstərici mərkəzə doğru hərəkət edir, ya biri irəli gedir, digəri isə yerində qalır).
3. Şərtin yoxlanması: Hər bir addımda göstəricilərin daha da hərəkəti və ya algoritmin bitməsini müəyyən edən bir şərt yoxlanılır.

Vaxt mürəkkəbliyi:

O(n) — əksər hallarda, çünki hər iki göstərici massiv üzərindən bir dəfə və ya bir neçə dəfə keçərək, ümumilikdə O(n)-dən çox iterasiya edə bilmir.

Bəzi tapşırıqlar üçün, şərtlərdən və göstəricilərin ilkin mövqeyindən asılı olaraq, vaxt mürəkkəbliyi O(n log n) və ya O(n^2) ola bilər, lakin bu nadir hallarda baş verir.

İki göstərici metodu ilə həll olunan tapşırıq nümunələri:

2.2 Verilmiş bir ədədi cəmi olan iki ədədin massivin içində axtarışı.

Tapşırıq:

Sıralanmış massivdə elə iki ədəd tap ki, onların cəmi target (təqdim olunan ədəd) olsun.

Həlli:

Bir göstəricini massivdə başlanğıc nöqtəsinə qoyuruq, digərini isə son nöqtəsinə. İndeksdəki ədədlərin cəmini yoxlayırıq:

• Əgər cəm target-ə bərabərdirsə, indeksləri qaytarırıq.
• Əgər cəm target-dən kiçikdirsə, sol göstəricini sağa hərəkət etdiririk.
• Əgər cəm target-dən böyükdürsə, sağ göstəricini sola hərəkət etdiririk.

Zaman mürəkkəbliyi: O(n).

Python-da nümunə kod:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 Palindrom yoxlaması

Tapşırıq:

Bir sətirin palindrom olub-olmadığını yoxlamaq.

Həll yolu:

Göstəriciləri sətirin başlanğıcı və sonuna təyin edirik. Göstəricilər altındakı simvolları müqayisə edirik:

• Əgər simvollar bərabərdirsə, hər iki göstəricini bir-birinə doğru hərəkət etdiririk.
• Əgər simvollar bərabər deyilsə, sətir palindrom deyil.

Zaman mürəkkəbliyi: O(n).

Python ilə kod nümunəsi:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 Sıralı massivdən təkrarlanan elementlərin silinməsi

Məsələ:

Sıralı massivdən təkrarlanan elementləri silin.

Həll:

İki göstəricidən istifadə edirik: biri nəticə massivindəki cari mövqeyi göstərir, digəri isə bütün elementləri keçmək üçün istifadə olunur:

• Əgər cari element əvvəlki eleməntdən fərqlidirsə, onu nəticə massivinə yazırıq.

Zaman mürəkkəbliyi: O(n).

Python-da kod nümunəsi:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index