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

  1. result bo'sh massivni ishga tushiring.
  2. Oxirgi elementdan tashqari, kirish massivida takrorlang. Biz oxirgi elementni tekshirishimiz shart emas, chunki u har doim -1 bilan almashtiriladi.
  3. Kirish massividagi tsiklning har bir indeksi i uchun result[i] ni o'ngdagi keyingi maksimal elementga o'rnating.
  4. 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

  1. max dan -1 gacha bo'lgan o'zgaruvchini ishga tushiring. Bu o'zgaruvchi hozirgacha duch kelgan maksimal elementni kuzatib boradi.
  2. arr kirish massivini eng o'ng elementdan takrorlang, chunki biz o'ng tomondan shu paytgacha duch kelgan maksimal elementni kuzatib borishni xohlaymiz.
  3. Har bir iteratsiya uchun o'zgaruvchini ishga tushiring va element qiymatini joriy indeksdagi arr[i] o'zgaruvchiga saqlang.
  4. Keyin, arr[i] kirish massividagi joriy indeks qiymatini biz hozirgacha ko'rgan, max variableda saqlanadigan maksimal qiymatga o'rnatamiz.
  5. 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"