Multiple pointers nümunəsi

codex

Multiple pointers nümunəsi indeks və ya mövqeyə uyğun olaraq göstəricilər və ya dəyərlər yaratmaq və müəyyən şərtlərə əsasən başlanğıc, son və ya orta hissəyə doğru hərəkət etdirmək üsuludur.

Problem

Bir sumZero funksiyası yazın. Bu funksiya sıralanmış tam ədədlər massivini qəbul edir. Funksiya cəmi 0 olan ilk cütlüyü tapmalıdır. Əgər belə bir cütlük mövcuddursa, onu massiv şəklində qaytarsın, əks halda undefined qaytarsın.

Naiv Həll

Bu üsul massivdəki hər bir elementi digər elementlərlə müqayisə edir. İki for dövrü istifadə olunduğu üçün zaman mürəkkəbliyi O(n²)-dir.

function sumZero(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                return [arr[i], arr[j]];
            }
        }
    }
}

sumZero([-4, -3, -2, -1, 0, 1, 2, 5]);

Çatışmazlıqlar:

Massiv çox böyük olduqda performans aşağı düşür.
Hər bir elementi digər elementlə müqayisə etdiyimiz üçün lazımsız təkrarlanmalara səbəb olur.

Multiple Pointer Həlli

Bu üsulda iki göstərici (pointer) istifadə edirik:

Sol pointer (left) – massivdəki ilk elementdən başlayır.
Sağ pointer (right) – massivdəki son elementdən başlayır.

Məntiq:

Əgər arr[left] + arr[right] === 0 isə, bu cütlük qaytarılır.
Əgər cəmi 0-dan böyükdürsə, sağ pointer (right--) bir vahid sola çəkilir.
Əgər cəmi 0-dan kiçikdirsə, sol pointer (left++) bir vahid sağa çəkilir.

Zaman mürəkkəbliyi O(n) olduğu üçün bu yanaşma daha effektivdir.

function sumZero(array) {
    let left = 0, right = array.length - 1;

    while (left < right) {
        let sum = array[left] + array[right];

        if (sum === 0) {
            return [array[left], array[right]];
        } else if (sum > 0) {
            right--;
        } else {
            left++;
        }
    }
}

sumZero([-4, -3, -2, -1, 0, 1, 2, 5]);

Üstünlüklər:
Yalnız bir while dövrü istifadə etdiyi üçün daha sürətlidir.
Yaddaş sərfiyyatı daha azdır.
Böyük massivlər üçün effektiv nəticə verir.

Nəticə

Multiple pointers nümunəsi çox vaxt O(n²) mürəkkəblikdən O(n) mürəkkəbliyə keçməyə imkan verir. Bu metod xüsusilə sıralanmış massivlərdə istifadə üçün əladır, axtarış və müqayisə məsələlərində performansı artırır.