Merge Sorted Array
Kamu mendapatkan dua array bilangan bulat, nums1 dan nums2. Masing-masing sudah diurutkan dalam urutan tidak menurun. Kembalikan satu array yang memuat semua nilai dari keduanya, juga dalam urutan tidak menurun. Nilai yang muncul di kedua array akan muncul dalam hasil sebanyak jumlah kemunculannya di kedua array.
Fungsi
- nums1integer-array
- array pertama yang diurutkan
- nums2integer-array
- array terurut kedua
- Mengembalikaninteger-array
- semua nilai dari kedua array dalam satu array terurut, dengan panjang nums1.length + nums2.length
Batasan
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105nums1dannums2masing-masing diurutkan dalam urutan tidak menurun.
Contoh
- Input
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- Output
- [1, 2, 3, 4, 9, 10]
- Penjelasan
- Bandingkan dua nilai di bagian depan dan pertahankan yang lebih kecil: 1, lalu 2 dan 3 dari
nums2, kemudian 4 dan 9 darinums1, dan terakhir 10. Hasilnya memuat keenam nilai.
- Input
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- Output
- [-5, 0, 0, 0, 6, 8]
- Penjelasan
- Angka 0 muncul dua kali di
nums1dan sekali dinums2, jadi hasilnya memiliki tiga angka 0. Angka -5 lebih kecil daripada semua angka dinums2dan muncul lebih dahulu.
- Input
- nums1 = [7]nums2 = [3]
- Output
- [3, 7]
- Penjelasan
- Setiap array menyimpan satu nilai. 3 lebih kecil dari 7, jadi angka itu diletakkan terlebih dahulu.
Pertanyaan lanjutan
Dapatkah kamu menggabungkan k array terurut yang secara total berisi N nilai, dalam waktu O(N log k)?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Kedua array sudah diurutkan. Di mana nilai terkecil dari seluruh hasil dapat ditemukan?
Nilai terkecil yang tersisa selalu berada di bagian depan
nums1atau di bagian depannums2. Gunakan satu indeks untuk setiap array guna menandai posisi bagian depan masing-masing.Bandingkan kedua elemen terdepan, tambahkan elemen yang lebih kecil, lalu majukan indeks tersebut. Saat salah satu array habis, sisa array lainnya sudah berurutan, jadi tambahkan apa adanya.
Solusi
Kedua array sudah diurutkan, jadi nilai terkecil yang tersisa selalu berada di bagian depan salah satunya. Simpan satu indeks untuk setiap array, ambil nilai terkecil di bagian depan pada setiap langkah, dan satu kali penelusuran akan membentuk hasilnya. Ini adalah langkah penggabungan dalam merge sort.
Gabungkan dan urutkan
Intuisi
Gabungkan kedua array dan urutkan hasilnya. Hasilnya memuat setiap nilai sebanyak kemunculannya, secara berurutan. Dengan m nilai dalam nums1 dan n dalam nums2, pengurutan memerlukan O((m + n) log(m + n)). Cara ini cukup cepat untuk batasan ini, tetapi mengabaikan urutan terurut yang diberikan kepadamu.
Algoritma
- Buat array dengan nilai
nums1diikuti nilainums2. - Urutkan array itu dalam urutan numerik menaik.
- Kembalikan array itu.
def merge(nums1, nums2):
return sorted(nums1 + nums2)Dua pointer, satu untuk setiap array
Intuisi
Indeks i dan j menandai nilai pertama yang belum digunakan dari setiap array. Tambahkan nilai yang lebih kecil antara nums1[i] dan nums2[j], lalu geser indeksnya. Setelah salah satu array habis digunakan, sisa nilai pada array lainnya sudah berurutan dan tinggal ditambahkan di bagian akhir.
Setiap langkah menulis satu nilai, jadi perulangan berjalan sebanyak m + n kali: waktu O(m + n), dengan hasil sebagai satu-satunya memori tambahan.
Algoritma
- Tetapkan
idanjke 0, lalu buat hasil kosong. - Selama kedua array masih memiliki nilai, bandingkan
nums1[i]dengannums2[j]. - Tambahkan nilai yang lebih kecil, lalu majukan indeksnya. Jika nilainya sama, pilih
nums1[i]. - Jika salah satu array habis, tambahkan sisa nilai dari array lainnya.
- Kembalikan hasilnya.
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
Jebakan dan kasus tepi
- Berhenti saat salah satu array habis dan lupa menyalin sisa elemen dari array lainnya. Dengan
[1, 2, 3]dan[4, 5, 6], perulangan berakhir setelah 1, 2, dan 3, sedangkan 4, 5, dan 6 masih harus disalin. - Membaca
nums1[i]setelahimencapai akhir. Periksa kedua indeks sebelum membandingkannya. - Menghilangkan duplikat.
[0, 0]dan[0]digabungkan menjadi[0, 0, 0], bukan[0]. - Di JavaScript dan TypeScript,
sort()tanpa pembanding mengurutkan angka sebagai teks, sehingga[-5, 10, 9]tetap menjadi[-5, 10, 9]. Berikan(a, b) => a - b.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu untuk menggabungkan dua array yang sudah diurutkan?
Dengan dua pointer, kompleksitasnya adalah O(m + n), dengan m dan n sebagai panjang masing-masing: setiap langkah menempatkan satu nilai. Menggabungkan lalu mengurutkan membutuhkan biaya O((m + n) log(m + n)).
Bagaimana cara menggabungkan dua array terurut secara langsung?
Jika array pertama memiliki ruang untuk keduanya di bagian akhirnya, isi dari belakang. Bandingkan nilai terbesar yang tersisa dari kedua array, tulis nilai yang lebih besar ke slot kosong terakhir, lalu geser ke kiri. Menulis dari belakang tidak akan menimpa nilai array pertama yang belum ditempatkan.
Apakah menggabungkan dua array yang sudah diurutkan sama dengan langkah penggabungan dalam merge sort?
Ya. Merge sort membagi array menjadi dua bagian, mengurutkan setiap bagian, lalu menggabungkan kedua bagian yang sudah diurutkan dengan perulangan dua pointer yang persis seperti ini. Mengambil nilai dari bagian kiri saat nilainya sama mempertahankan urutan awal nilai-nilai yang sama, sehingga merge sort stabil.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def merge(nums1, nums2):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
Output yang diharapkan
[1, 2, 3, 4, 9, 10]