JavaScript-da ushbu muammoni hal qilish uchun turli yondashuvlar
Muammo bayoni:
arr
massivi berilgan bo'lsa, ushbu massivdagi har bir elementni o'ng tomonidagi elementlarning eng katta elementi bilan almashtiring va oxirgi elementni-1
bilan almashtiring. Buni qilgandan so'ng, massivni qaytaring.
Xo'sh, bu muammoni qanday hal qilishimiz mumkin?
1-yondashuv:JavaScript-da o'rnatilgan funksiyalardan foydalanish
result
bo'sh massivni ishga tushiring.- Oxirgi elementdan tashqari, kirish massivida takrorlang. Biz oxirgi elementni tekshirishimiz shart emas, chunki u har doim -1 bilan almashtiriladi.
- Kirish massividagi tsiklning har bir indeksi
i
uchunresult[i]
ni o'ngdagi keyingi maksimal elementga o'rnating. - Keyingimaksimal,
Math.max()
,.slice()
va... (spread operator)
yordamida topiladi.
// ES6 Arrow Function const replaceMaxRight = arr => { const result = []; for(let i = 0; i < arr.length; i++) { result[i] = Math.max(...arr.slice(i+1)); } result[result.length - 1] = -1; return result; }
Vaqt murakkabligi:O(N²)
Kosmik murakkablik:O(N)
Eslatma:Avvalgi yechim ishlayotgan bo'lsa-da, u eng samarali emas, chunki uning vaqt murakkabligi O(N²). Biroq, massivni o'ngdan chapga takrorlash orqali vaqt murakkabligini O(N) ga oshirishimiz mumkin. Keling, ushbu muammoni hal qilish uchun ikkinchi yondashuvimizda buni ko'rib chiqaylik.
2-yondashuv:Kirish massivini oʻngdan chapga takrorlash
max
dan-1
gacha bo'lgan o'zgaruvchini ishga tushiring. Bu o'zgaruvchi hozirgacha duch kelgan maksimal elementni kuzatib boradi.arr
kirish massivini eng o'ng elementdan takrorlang, chunki biz o'ng tomondan shu paytgacha duch kelgan maksimal elementni kuzatib borishni xohlaymiz.- Har bir iteratsiya uchun o'zgaruvchini ishga tushiring va element qiymatini joriy indeksdagi
arr[i]
o'zgaruvchiga saqlang. - Keyin,
arr[i]
kirish massividagi joriy indeks qiymatini biz hozirgacha ko'rgan,max
variableda saqlanadigan maksimal qiymatga o'rnatamiz. - Nihoyat, joriy maksimal qiymatni 3-bosqichda saqlagan qiymat bilan solishtirish orqali
max
o‘zgaruvchining qiymatini yangilaymiz. Agar biz saqlagan qiymat joriy maksimal qiymatdan kattaroq bo‘lsa,max
o‘zgaruvchisini mos ravishda yangilaymiz.
// ES6 Arrow Functions const replaceMaxRight = arr => { let max = -1; for(let i = arr.length - 1; i >= 0; i--) { let curr = arr[i]; arr[i] = max; max = Math.max(max, curr); } return arr; }
Vaqt murakkabligi:O(N)
Kosmik murakkablik:O(1)
Eslatma:Ikkinchi yondashuvdan biroz farq qiladigan muammoni kodlashning yana bir usuli.
// ES6 Arrow Function const replaceMaxRight = arr => { let max = arr[arr.length - 1]; arr[arr.length - 1] = -1; for(let i = arr.length - 2; i >= 0; i--) { let curr = arr[i]; arr[i] = max; if(curr > max) max = curr; } return arr; }
Eslatma:VaqtvaMakonmurakkabligi 2-yondashuvdagi kabi bir xil boʻlib qoladi.
Umid qilamanki, ushbu maqola sizga qimmatli fikrlarni taqdim etdi va ushbu muammoni hal qilishning turli usullarini yaxshiroq tushunishga yordam berdi. Baxtli kodlash!
Muammo - "Leetcode 1299"