Nollarni ortga surish
Bu masala ikki ko'rsatkich (two pointers) texnikasining klassik namunasi. Unda massivni boshqa massiv yaratmasdan joyida o'zgartirish va elementlarning nisbiy tartibini saqlash kerak bo'ladi.
Masala
Sonlar massivi berilgan. Undagi barcha 0larni massivning oxiriga surish kerak. Bunda nolsiz elementlarning nisbiy tartibi saqlanib qolishi shart.
Kirish: [0, 1, 0, 3, 12]
Chiqish: [1, 3, 12, 0, 0]
Kirish: [0, 0, 1]
Chiqish: [1, 0, 0]
Kirish: [1, 2, 3]
Chiqish: [1, 2, 3] (nol yo'q, o'zgarmaydi)
Shartlar:
- massivni joyida o'zgartirish (O(1) qo'shimcha xotira);
- nolsiz elementlarning tartibi saqlanishi kerak.
Dastlabki g'oya — yangi massivga yozish
Birinchi instinkt: yangi massiv yaratib, avval barcha nolsiz elementlarni yozib, keyin oxiriga nollarni qo'shish. Bu to'g'ri ishlaydi va kodni tushunarli qiladi.
FUNCTION nollarni_sur_yangi(array)
natija = bo'sh massiv
FOR har bir element array ichida
IF element ≠ 0
natijaga element QOSH
WHILE natija uzunligi < array uzunligi
natijaga 0 QOSH
RETURN natija
Bu O(n) vaqt va O(n) xotira talab qiladi. Lekin masala shartida O(1) xotira talab qilingan. Yangi massiv yaratish bu shartni buzadi.
Optimal yondashuv — ikki ko'rsatkich
Yangi massiv yaratmasdan, asl massivni joyida o'zgartirish mumkin. Buning uchun ikkita ko'rsatkich ishlatiladi:
yozish— nolsiz elementlarning yoziladigan joyini ko'rsatadi;o'qish— massivni boshidan oxirigacha ketma-ket ko'rib chiqadi.
G'oya sodda: o'qish ko'rsatkichi nolsiz element topsagina, uni yozish ko'rsatkichining joyi bilan almashtirib, yozishni oldinga siljitadi. Nollarni alohida joylashtirish kerak emas — ular o'z-o'zidan orqaga qoladi.
FUNCTION nollarni_sur(array)
yozish = 0
FOR o'qish = 0 DAN array uzunligi - 1 GACHA
IF array[o'qish] ≠ 0
array[yozish] VA array[o'qish] JOYINI ALMASHTIR
yozish = yozish + 1
Bosqichma-bosqich tahlil
[0, 1, 0, 3, 12] massivini ko'rib chiqamiz:
Boshlang'ich:
[0, 1, 0, 3, 12]
↑ yozish = 0
↑ o'qish = 0
o'qish=0: array[0]=0 → nol, o'tkazib yuboriladi. o'qish++
o'qish=1: array[1]=1 → nolsiz.
array[0] ↔ array[1] almashtiriladi
[1, 0, 0, 3, 12]
↑ yozish = 1
↑ o'qish = 2
o'qish=2: array[2]=0 → nol, o'tkazib yuboriladi. o'qish++
o'qish=3: array[3]=3 → nolsiz.
array[1] ↔ array[3] almashtiriladi
[1, 3, 0, 0, 12]
↑ yozish = 2
↑ o'qish = 4
o'qish=4: array[4]=12 → nolsiz.
array[2] ↔ array[4] almashtiriladi
[1, 3, 12, 0, 0]
↑ yozish = 3
↑ o'qish = 5
o'qish massiv chegarasidan chiqdi. To'xtaymiz.
Natija: [1, 3, 12, 0, 0] ✓
yozish ko'rsatkichi har doim "nolsiz elementlar qismi"ning o'ng chegarasini ko'rsatadi. yozish indexidan keyingi barcha elementlar oxir-oqibat nol bo'ladi.
Nima uchun tartib saqlanadi?
o'qish chapdan o'ngga ketma-ket yuradi. U nolsiz elementni topsagina yozish joyi bilan almashtiradi. Shu sababli nolsiz elementlar o'z chap-o'ng tartibida yozish ko'rsatkichi o'tadigan joylarga yoziladi. Ular o'zaro almashtirilmaydi — faqat yozish joyi bilan.
1 → birinchi nolsiz element, 0-joyga yoziladi
3 → ikkinchi nolsiz element, 1-joyga yoziladi
12 → uchinchi nolsiz element, 2-joyga yoziladi
Tartib o'zgarmadi.
Murakkablik
Vaqt murakkabligi: O(n) — o'qish massiv bo'ylab bir marta yuradi.
Xotira murakkabligi: O(1) — faqat yozish o'zgaruvchisi. Yangi massiv yaratilmaydi.
Muhim hollar
Nol yo'q: [1, 2, 3]. Har bir element nolsiz, shuning uchun har safar array[yozish] ↔ array[o'qish] almashtiriladi. Aslida element o'zi bilan o'zi almashtiriladi — massiv o'zgarmaydi. Natija to'g'ri.
Hamma nol: [0, 0, 0]. yozish hech qachon siljimaydi. Barcha elementlar o'qish tomonidan o'tkazib yuboriladi. Massiv o'zgarmaydi. Natija to'g'ri.
Boshida nollar: [0, 0, 1, 2]. yozish = 0 da qoladi, o'qish = 2da 1 topiladi, array[0] ↔ array[2] almashtiriladi. Natija [1, 0, 0, 2], keyin [1, 2, 0, 0]. To'g'ri.
Bitta element: [0] yoki [5]. Tsikl bir marta ishlaydi yoki nolsiz almashtirish bajarilmaydi. To'g'ri.
Tip
Agar masala shartida "nolsiz elementlarning tartibini saqlash shart emas" deyilsa, yondashuv soddalashishi mumkin: yozish ko'rsatkichi boshdan, boshqa ko'rsatkich oxirdan harakat qilib, nol va nolsizlarni joylashtirish mumkin. Lekin bu tartibni buzadi — masala shartini har doim diqqat bilan o'qing.
Qaysi texnika ishlatildi?
Bu masalada ikki ko'rsatkich — bir yo'nalishda (slow-fast) texnikasi qo'llanildi. yozish — sekin ko'rsatkich, faqat nolsiz element topilganda siljiydi. o'qish — tez ko'rsatkich, har qadam oldinga ketadi. Bu texnika massivdan ma'lum elementlarni filtrlash yoki qismlarni ajratish uchun keng ishlatiladi.