Apa itu Merge Sorted Array?
"Merge Sorted Array" adalah masalah yang sering muncul dalam pemrograman, terutama dalam konteks pengolahan data terurut. Masalah ini meminta Anda untuk menggabungkan dua array yang sudah diurutkan (sorted) menjadi satu array yang juga diurutkan.
Secara khusus, masalah ini sering kali dinyatakan dalam bentuk berikut:
Anda diberikan dua array, misalnya `nums1` dan `nums2`, yang sudah diurutkan dalam urutan non-menurun (artinya elemen-elemennya terurut dari yang terkecil hingga yang terbesar). Array pertama, `nums1`, memiliki elemen-elemen yang sudah diurutkan dan memiliki cukup ruang kosong di belakangnya untuk menampung elemen-elemen dari array kedua, `nums2`. Anda juga diberikan informasi tentang berapa banyak elemen yang sebenarnya ada di setiap array, yaitu `m` untuk `nums1` dan `n` untuk `nums2`.
Tugas Anda adalah menggabungkan kedua array ini sehingga hasilnya adalah satu array yang juga diurutkan dalam urutan non-menurun. Hasilnya harus dimasukkan ke dalam array pertama (`nums1`) tanpa menggunakan array tambahan untuk menyimpan hasil penggabungan.
Contohnya, jika `nums1` adalah `[1, 2, 3, 0, 0, 0]` dengan `m = 3`, dan `nums2` adalah `[2, 5, 6]` dengan `n = 3`, maka hasil penggabungannya adalah `[1, 2, 2, 3, 5, 6]`. Di sini, elemen-elemen dari `nums1` dan `nums2` telah digabungkan menjadi satu array yang diurutkan.
Masalah ini sering muncul dalam konteks penggabungan data terurut, seperti saat menggabungkan dua daftar atau array yang telah diurutkan untuk menghasilkan hasil yang juga diurutkan. Solusi yang efisien biasanya melibatkan penggunaan algoritma dua-pointer seperti yang telah dijelaskan sebelumnya untuk menggabungkan array dalam waktu linier O(m + n).
Tentu, mari saya jelaskan dengan lebih detail algoritma yang baru saja saya paparkan: 1. Pertama-tama, kita menginisialisasi tiga pointer: - `index1`: Pointer yang menunjuk ke elemen terakhir dalam array `nums1` yang akan digunakan dalam penggabungan. - `index2`: Pointer yang menunjuk ke elemen terakhir dalam array `nums2` yang akan digunakan dalam penggabungan. - `mergedIndex`: Pointer yang menunjuk ke posisi terakhir dalam array yang akan menjadi hasil penggabungan (ini adalah posisi terakhir dalam `nums1`). 2. Kita masuk ke dalam loop while utama yang akan terus berjalan selama kedua pointer `index1` dan `index2` masih valid (lebih besar dari atau sama dengan nol). 3. Di dalam loop, kita membandingkan elemen yang ditunjuk oleh `index1` di `nums1` dan elemen yang ditunjuk oleh `index2` di `nums2`. Kita membandingkan elemen tersebut untuk menentukan elemen mana yang lebih besar. 4. Jika elemen di `nums1` yang ditunjuk oleh `index1` lebih besar, maka elemen tersebut akan ditempatkan di posisi `mergedIndex` di dalam `nums1`, dan `index1` akan mundur satu langkah. 5. Jika elemen di `nums2` yang ditunjuk oleh `index2` lebih besar atau sama, maka elemen tersebut akan ditempatkan di posisi `mergedIndex` di dalam `nums1`, dan `index2` akan mundur satu langkah. 6. Pointer `mergedIndex` akan mundur satu langkah setelah menggabungkan satu elemen. 7. Proses ini akan terus berlanjut hingga salah satu dari pointer `index1` atau `index2` habis (lebih kecil dari nol). Hal ini menjamin bahwa semua elemen dari `nums2` akan digabungkan ke dalam `nums1` sesuai urutan yang benar. 8. Setelah loop selesai, jika masih ada elemen yang tersisa di `nums2`, kita akan menyalin sisa elemen-elemen ini ke dalam `nums1` mulai dari posisi `mergedIndex` hingga `index2` habis. Hasil akhir dari algoritma ini adalah penggabungan dari kedua array, `nums1` dan `nums2`, yang sudah diurutkan secara tidak menurun dalam array `nums1`. Algoritma ini bekerja dengan efisien dengan waktu yang berjalan secara linier O(m + n), di mana m adalah panjang `nums1` dan n adalah panjang `nums2`. Ini merupakan solusi yang optimal sesuai dengan constraint yang diberikan dalam masalah ini.
public void merge(int[] nums1, int m, int[] nums2, int n) { int index1 = m - 1; // Index of the last element in nums1 int index2 = n - 1; // Index of the last element in nums2 int mergedIndex = m + n - 1; // Index of the last position in the merged array (nums1) while (index1 >= 0 && index2 >= 0) { if (nums1[index1] > nums2[index2]) { nums1[mergedIndex] = nums1[index1]; index1--; } else { nums1[mergedIndex] = nums2[index2]; index2--; } mergedIndex--; } // If there are remaining elements in nums2, copy them to nums1 while (index2 >= 0) { nums1[mergedIndex] = nums2[index2]; index2--; mergedIndex--; } }
Tidak ada komentar:
Posting Komentar