Median of Two Sorted Arrays
Kamu mendapatkan dua list bilangan bulat, nums1 dan nums2, yang masing-masing diurutkan dari terkecil ke terbesar dan berisi setidaknya satu nilai. Kembalikan median dari semua nilainya jika digabungkan, dalam bentuk teks.
Untuk jumlah total yang ganjil, median adalah nilai tengah, seperti "4". Untuk jumlah yang genap, median adalah rata-rata dari dua nilai tengah, seperti "2.5" atau "-0.5". Tulis bilangan bulat tanpa titik desimal, dan tulis nol sebagai "0", jangan pernah "-0". Usahakan waktu O(log(min(m, n))).
Fungsi
- nums1integer-array
- daftar pertama, diurutkan dari yang terkecil hingga terbesar
- nums2integer-array
- list kedua, diurutkan dari yang terkecil hingga yang terbesar
- Mengembalikanstring
- median dari semua nilai, sebagai teks seperti "4" atau "-2.5"
Batasan
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Kedua list diurutkan dalam urutan tidak menurun, dan nilainya dapat berulang.
Contoh
- Input
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Output
- "4"
- Penjelasan
- Jika digabungkan, nilainya adalah 1, 2, 4, 7, 9. Dari lima nilai, ada satu nilai tengah, yaitu nilai ketiga, yakni 4.
- Input
- nums1 = [1, 2]nums2 = [3, 4]
- Output
- "2.5"
- Penjelasan
- Jika digabungkan, nilainya adalah 1, 2, 3, 4. Dua nilai tengahnya adalah 2 dan 3, jumlahnya 5, dan setengah dari 5 adalah 2.5.
- Input
- nums1 = [-7, -3]nums2 = [-2, 0]
- Output
- "-2.5"
- Penjelasan
- Jika digabungkan, nilainya adalah -7, -3, -2, 0. Nilai tengahnya, -3 dan -2, jika dijumlahkan menjadi -5, dan setengah dari -5 adalah -2.5.
Pertanyaan lanjutan
Bisakah kamu menggunakan pembagian yang sama untuk menemukan nilai terkecil ke-k dari kedua list, untuk sembarang k, dalam waktu logaritmik?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Menggabungkan kedua list akan menemukan median dalam
O(m + n). Agar lebih efisien, bayangkan median sebagai batas: sebuah garis yang membagi semuam + nnilai menjadi bagian bawah dan bagian atas yang berukuran sama.Setengah bagian bawah adalah prefiks dari
nums1ditambah prefiks darinums2. Jika kamu mengambilinilai darinums1, jumlah nilai darinums2mengikuti. Pembagian sudah tepat jika nilai terakhir yang diambil dari setiap list tidak lebih besar daripada nilai pertama yang tersisa di list lainnya.Lakukan pencarian biner pada
idi dalam list yang lebih pendek. Jika nilai terakhir yang diambil darinums1terlalu besar, ambil lebih sedikit dari list itu; jika nilai terakhir yang diambil darinums2terlalu besar, ambil lebih banyak. Pada pemisah yang tepat, median berasal dari nilai terbesar di bawah pemisah dan nilai terkecil di atasnya. Jumlahkan kedua bilangan bulat itu, lalu bagi dua sendiri.
Solusi
Menggabungkan kedua list menghasilkan median dalam O(m + n), tetapi sebagian besar nilai yang dibaca tidak dapat mengubah jawabannya. Median hanya bergantung pada posisi batas antara bagian bawah dan bagian atas, dan satu angka menentukan batas tersebut: jumlah nilai yang diambil bagian bawah dari list yang lebih pendek. Binary search menemukannya dalam O(log(min(m, n))) langkah.
Gabungkan kedua list
Intuisi
Gabungkan list seperti yang dilakukan merge sort, menjadi satu list terurut merged. Dengan total = m + n, tambahkan merged[(total-1)/2] dan merged[total/2], dengan menggunakan pembagian bilangan bulat. Untuk total ganjil, keduanya adalah nilai tengah. Untuk total genap, keduanya adalah dua nilai tengah, jadi setengah dari jumlahnya adalah median dalam kedua kasus.
Meskipun kamu berhenti di bagian tengah, langkah-langkah penggabungan melewati lebih dari setengah nilai, jadi waktunya adalah O(m + n).
Algoritma
- Gabungkan list ke dalam
merged, selalu ambil nilai terkini yang lebih kecil, lalu tambahkan sisa list yang masih ada. - Dengan
total = m + n, jumlahkanmerged[(total-1)/2]danmerged[total/2]. - Kembalikan setengah dari jumlah tersebut sebagai teks: bagi jumlah genap dengan 2; untuk jumlah ganjil, tulis tandanya, setengah dari nilai absolutnya, dan
.5.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])Pencarian biner pada potongan
Intuisi
Biarkan separuh bagian bawah menampung half = (m+n+1)/2 nilai, dengan satu nilai tambahan jika jumlah totalnya ganjil. Bagian ini mengambil i nilai dari awal nums1 dan j = half-i nilai dari awal nums2. Pemisahannya tepat jika tidak ada nilai di bagian bawah yang lebih besar daripada nilai apa pun di bagian atas. Setiap list sudah terurut, jadi tersisa dua pemeriksaan: left1 ≤ right2 dan left2 ≤ right1, dengan left sebagai nilai terakhir yang diberikan sebuah list ke bagian bawah dan right sebagai nilai pertama yang disimpan di bagian atas. Sisi yang tidak ada dihitung sebagai minus atau plus tak terhingga.
Jika left1 > right2, nilai i terlalu besar; jika left2 > right1, nilainya terlalu kecil. Jadi, pencarian biner untuk i dilakukan dari 0 hingga m. Pada [1, 2] dan [3, 4], i = 1 gagal karena left2 = 3 > right1 = 2, sedangkan i = 2 berhasil: (2 + 3) / 2 = 2.5.
Algoritma
- Jadikan
nums1sebagai list yang lebih pendek; tetapkanhalf = (m+n+1)/2. - Lakukan pencarian biner untuk
idarilo = 0hinggahi = m, denganj = half-i. - Baca
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]danright2 = nums2[j], dengan nilai tak terhingga setelah ujung. - Jika
left1 > right2, tetapkanhi = i-1. Jikaleft2 > right1, tetapkanlo = i+1. - Jika tidak, untuk jumlah total ganjil, kembalikan
max(left1, left2). Untuk jumlah total genap, bagi duamax(left1, left2) + min(right1, right2)sebagai teks.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
Jebakan dan kasus tepi
- Membagi dengan bilangan floating point. Python mencetak median bilangan bulat sebagai
3.0, dan%fdi C mencetak 2.5 sebagai2.500000. Pertahankan jumlahnya sebagai bilangan bulat. - Menulis hasil bagi bilangan bulat dan
.5untuk jumlah ganjil negatif.-1 / 2bernilai 0 di C dan Java, sehingga menghasilkan 0.5 untuk -0.5;-5 // 2bernilai -3 di Python, sehingga menghasilkan -3.5 untuk -2.5. Bagi nilai absolutnya dengan 2, lalu kembalikan tandanya. - Menulis
-0. Nilai tengah -1 dan 1 berjumlah 0, dan jawabannya adalah"0". Ambil tanda dari jumlahnya. - Mencari di list yang lebih panjang.
j = half-ibisa kurang dari 0 atau melebihin. Tukar list terlebih dahulu. - Membaca
nums1[i-1]saati = 0, seperti pada[9]dan[1, 2]. Gunakan nilai tak hingga untuk nilai yang tidak ada.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu dari Median of Two Sorted Arrays?
Pencarian biner pada titik pemisah memerlukan waktu O(log(min(m, n))) dan ruang O(1), karena setiap langkah membagi dua kemungkinan titik pemisah pada list yang lebih pendek. Penggabungan memerlukan waktu O(m + n): untuk dua list yang masing-masing berisi 3000 elemen, sekitar 12 langkah dibandingkan dengan 6000.
Mengapa melakukan binary search pada array yang lebih pendek?
Karena j = half-i. Saat i berada dalam list yang lebih pendek, j tetap di antara 0 dan panjang list yang lebih panjang, sehingga setiap pembacaan berada dalam rentang atau melewati ujung yang kamu perlakukan sebagai tak hingga.
Bagaimana cara mengembalikan median tanpa menggunakan bilangan pecahan?
Jumlahkan dua nilai tengah sebagai bilangan bulat. Bagi jumlah genap dengan 2. Untuk jumlah ganjil, tulis setengah dari nilai absolutnya dan .5, dengan tanda minus jika jumlahnya negatif: -1 menjadi "-0.5".
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def findMedianSortedArrays(nums1, nums2):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums1 = [1, 4] nums2 = [2, 7, 9]
Output yang diharapkan
"4"