Tarkibga o'tish

Ro'yxatni aylantirish

Massivni aylantirish (rotate) — elementlarni belgilangan miqdorda bir tomonga siljitish. Bu masala turli yo'llar bilan yechilishi mumkin va yechimlar orasidagi farq xotira sarfida keskin bo'ladi. Masala shuningdek "teskari aylantirish" hiylasini o'rgatadi — oddiy amalni uch marta qo'llash orqali murakkab natijaga erishish.

Masala

n uzunlikdagi massiv va k son berilgan. Massivni o'ng tomonga k qadam aylantirish kerak. Ya'ni, har bir element k katak o'ngga siljiydi; oxiridagi elementlar esa boshiga o'tadi.

Kirish:  [1, 2, 3, 4, 5, 6, 7], k = 3
Chiqish: [5, 6, 7, 1, 2, 3, 4]

Kirish:  [−1, −100, 3, 99], k = 2
Chiqish: [3, 99, −1, −100]

Izoh: k massiv uzunligidan katta bo'lishi mumkin. k = 10, massiv uzunligi 7 bo'lsa, aslida 10 % 7 = 3 qadam aylantiriladi.

Dastlabki g'oya — bitta-bitta aylantirish

Eng sodda yondashuv: massivni k marta, har safar 1 qadam aylantirishni takrorlash.

Bir marta 1 qadam o'ngga aylantirish: - Oxirgi elementni saqla. - Barcha elementlarni bir katak o'ngga sur. - Saqlab qo'yilgan elementni birinchi katakka qo'y.

FUNCTION bir_qadam(array)
    oxirgi = array[n - 1]
    FOR i = n - 1 DAN 1 GACHA
        array[i] = array[i - 1]
    array[0] = oxirgi

FUNCTION aylantir_bitta_bitta(array, k)
    k = k % array uzunligi
    FOR i = 1 DAN k GACHA
        bir_qadam(array)

Murakkablik: O(n × k) vaqt, O(1) xotira. k katta bo'lsa, bu juda sekin.

Ikkinchi g'oya — qo'shimcha massiv

Kattaroq, lekin tushunarliroq yondashuv: yangi massiv yaratilib, har bir element to'g'ri joyiga yoziladi.

i-indexdagi element (i + k) % n-indexga ko'chishi kerak:

FUNCTION aylantir_yangi(array, k)
    n = array uzunligi
    k = k % n
    yangi = n o'lchamli bo'sh massiv

    FOR i = 0 DAN n - 1 GACHA
        yangi[(i + k) % n] = array[i]

    FOR i = 0 DAN n - 1 GACHA
        array[i] = yangi[i]

[1, 2, 3, 4, 5, 6, 7], k = 3

element 1 (i=0) → yangi[(0+3)%7] = yangi[3]
element 2 (i=1) → yangi[(1+3)%7] = yangi[4]
element 3 (i=2) → yangi[(2+3)%7] = yangi[5]
element 4 (i=3) → yangi[(3+3)%7] = yangi[6]
element 5 (i=4) → yangi[(4+3)%7] = yangi[0]
element 6 (i=5) → yangi[(5+3)%7] = yangi[1]
element 7 (i=6) → yangi[(6+3)%7] = yangi[2]

yangi = [5, 6, 7, 1, 2, 3, 4] ✓

Murakkablik: O(n) vaqt, O(n) xotira. Tez, lekin qo'shimcha massiv kerak.

Optimal yondashuv — uch marta teskari aylantirish

Eng samarali yondashuv: massivni uchta kichik bosqichda teskari aylantirib, natijalari kombinatsiyasidan maqsadga erishish. Bu O(n) vaqt va O(1) xotira beradi.

Mantiq:

Asl:       [1, 2, 3, 4, 5, 6, 7], k = 3
Maqsad:    [5, 6, 7, 1, 2, 3, 4]

Kuzating: - [5, 6, 7] — aslning oxirgi k = 3 ta elementi; - [1, 2, 3, 4] — aslning birinchi n - k = 4 ta elementi.

Uch qadam:

  1. Butun massivni teskari aylantir: [7, 6, 5, 4, 3, 2, 1]
  2. Birinchi k ta elementni teskari aylantir: [5, 6, 7, 4, 3, 2, 1]
  3. Qolgan n - k ta elementni teskari aylantir: [5, 6, 7, 1, 2, 3, 4]
FUNCTION teskari_oraliq(array, chap, o'ng)
    WHILE chap < o'ng
        array[chap] VA array[o'ng] JOYINI ALMASHTIR
        chap = chap + 1
        o'ng = o'ng - 1

FUNCTION aylantir(array, k)
    n = array uzunligi
    k = k % n

    teskari_oraliq(array, 0, n - 1)
    teskari_oraliq(array, 0, k - 1)
    teskari_oraliq(array, k, n - 1)

Bosqichma-bosqich tahlil

[1, 2, 3, 4, 5, 6, 7], k = 3 uchun:

1-qadam: Butun massivni teskari aylantir:

[1, 2, 3, 4, 5, 6, 7]
 ↑                 ↑
Almashtirish: 1 ↔ 7 → [7, 2, 3, 4, 5, 6, 1]
              2 ↔ 6 → [7, 6, 3, 4, 5, 2, 1]
              3 ↔ 5 → [7, 6, 5, 4, 3, 2, 1]

Natija: [7, 6, 5, 4, 3, 2, 1]

2-qadam: Birinchi k = 3 ta elementni teskari aylantir (index 0..2):

[7, 6, 5, 4, 3, 2, 1]
 ↑     ↑
7 ↔ 5 → [5, 6, 7, 4, 3, 2, 1]

Natija: [5, 6, 7, 4, 3, 2, 1]

3-qadam: Qolgan n - k = 4 ta elementni teskari aylantir (index 3..6):

[5, 6, 7, 4, 3, 2, 1]
          ↑        ↑
4 ↔ 1 → [5, 6, 7, 1, 3, 2, 4]
3 ↔ 2 → [5, 6, 7, 1, 2, 3, 4]

Natija: [5, 6, 7, 1, 2, 3, 4] ✓

Nima uchun bu ishlaydi?

Butun massivni teskari aylantirganingizda, oxirgi k ta element boshiga keladi — lekin teskari tartibda. Ikkinchi qadamda shu k ta elementni teskari aylantirsangiz, ular to'g'ri tartibga keladi. Uchinchi qadamda qolgan qismni teskari aylantirsangiz, ular ham to'g'ri tartibga kiradi.

Bu g'oya algebraga asoslanadi. Teskari aylantirish operatsiyasi — o'z inversiga teng. Ikki marta teskari aylantirish asl holatni qaytaradi.

Murakkablik

Yondashuv Vaqt Xotira
Bitta-bitta aylantirish O(n × k) O(1)
Qo'shimcha massiv O(n) O(n)
Uch marta teskari aylantirish O(n) O(1)

Uch marta teskari aylantirish usulida 3 marta teskari aylantirish bajariladi, har biri O(n). Jami O(3n), ya'ni O(n). Xotira faqat almashtirish uchun bitta o'zgaruvchi — O(1).

Muhim hollar

k = 0: Aylantirish bo'lmaydi. k % n = 0, barcha operatsiyalar bo'sh oraliqda bajariladi. Massiv o'zgarmaydi.

k = n: To'liq bir aylanish. k % n = 0. Massiv o'zgarmaydi.

k > n: k % n orqali haqiqiy qadam soniga keltiriladi.

Bitta element: n = 1, k % 1 = 0. Massiv o'zgarmaydi.

Manfiy aylantirish: Ba'zi masalalar chap tomonga aylantirish ham so'raydi. Chap tomonga k qadam = o'ng tomonga n - k qadam.

Warning

k % n hisoblashni unutmaslik kerak. Aks holda k = 14, n = 7 bo'lsa, ikki marta to'liq aylantirish amalga oshiriladi — bu qimmat va noto'g'ri.

Qaysi texnika ishlatildi?

Bu masalada teskari aylantirish (reverse) texnikasi qo'llanildi. Oddiy amalni — elementlarni almashtirish — uch marta turli oraliqda qo'llash orqali murakkab natijaga erishiladi. Bu "qurilish bloklari" yondashuvi: oddiy operatsiyalardan murakkab transformatsiya yasash.

📍 Toshkent, O'zbekiston
🗓️
👤