Temuduga Teratas 150

Menggabungkan tatasusunan yang diisih ialah masalah klasik dan memahami cara menyelesaikannya dengan cekap adalah penting untuk temu bual pengekodan. Dalam siaran ini, kami akan menangani LeetCode's 88. Merge Sorted Array, sebahagian daripada cabaran Top Interview 150 Questions, menggunakan JavaScript. Mari selami masalah, nuansanya, dan penyelesaian yang bersih dan optimum!

? Huraian Masalah
Anda diberi dua tatasusunan integer nums1 dan nums2, diisih dalam susunan tidak menurun. Tugas anda adalah untuk menggabungkan nums2 menjadi nums1, supaya nums1 kekal diisih.

Namun, terdapat kelainan:

nums1 mempunyai ruang yang mencukupi (ditetapkan kepada 0s) untuk memuatkan elemen nums2.
Hasil gabungan akhir mesti disimpan di tempat dalam nums1.

? Contoh

Contoh 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Contoh 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Contoh 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

? Wawasan Utama

• Gabungan di tempat: Anda perlu mengisi nombor1 tanpa menggunakan ruang tambahan. Ini bermakna mengubah suai tatasusunan secara terus.
• Strategi belakang ke hadapan: Memandangkan nums1 mempunyai ruang tambahan pada penghujungnya, pendekatan yang paling berkesan ialah mengisinya dari belakang.

? Penyelesaian JavaScript: Pendekatan Dua Penunjuk

Penyelesaian optimum memanfaatkan pendekatan dua mata, bermula dari penghujung kedua-dua tatasusunan. Ini memastikan elemen terbesar diletakkan dahulu, mengelakkan peralihan elemen yang tidak perlu.

var merge = function(nums1, m, nums2, n) {
    // Initialize pointers for nums1, nums2, and the last index of nums1
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    // Compare elements from the end and place the largest at the back
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // Copy remaining elements from nums2 (if any)
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
};

? Cara Ia Berfungsi

1. Mula dari akhir:
   Bandingkan elemen terbesar nums1 dan nums2 (menggunakan p1
   dan penunjuk p2). Letakkan elemen yang lebih besar di hujung
   nums1 (menggunakan p penunjuk).

2. Petunjuk penurunan:
   Gerakkan p1, p2 dan p semasa anda memproses elemen.

3. Kendalikan elemen yang tinggal:
   Jika ada unsur dalam nums2 yang tertinggal, salinnya ke dalam nums1. (Tidak
   perlu menyalin elemen daripada nums1, kerana ia sudah sedia ada.)

? Analisis Kerumitan

? Larian Kering
Input:
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Langkah p1 p2 p nums1
Init 2 2 5 [1,2,3,0,0,0]
1 2 2 5 [1,2,3,0,0,6]
2 2 1 4 [1,2,3,0,5,6]
3 2 0 3 [1,2,3,3,5,6]
4 1 0 2 [1,2,2,3,5,6]
5 0 0 1 [1,2,2,3,5,6]
Output Akhir: [1,2,2,3,5,6]

? Cubalah Sendiri!

Lihat masalah penuh dan kes ujian pada LeetCode. Cabar diri anda untuk melaksanakan penyelesaian tanpa melihat kod!

? Petua Pro untuk Temuduga

1. Jelaskan kekangan: Tanya sama ada anda boleh menggunakan ruang tambahan atau jika di- tempat adalah wajib.
2. Optimumkan untuk kes tepi: Pertimbangkan kes di mana nums2 kosong atau nums1 tidak mempunyai unsur awal (m = 0).
3. Telusuri logik anda: Terangkan pendekatan dua mata jelas kepada penemuduga.

Ada sebarang soalan atau pandangan? Kongsi mereka dalam komen di bawah! Mari belajar bersama. ?

Atas ialah kandungan terperinci Cabaran LeetCode: Gabungkan Tatasusunan Isih - Penyelesaian JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!