Leetcode 4. Median of Two Sorted Arrays

m va n uzunlikdagi tartiblangan nums1 and nums2 array’lar berilgan. Ikki array’ning medianini toping. Time complexity O(log(m + n)) bo’lsin.

Misol:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Tushuntirish: birlashtirilgan array = [1,2,3] va median = 2.

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Tushuntirish: birlashtirilgan array = [1,2,3,4] va median (2 + 3) / 2 = 2.5.

Median – tartiblangan array yoki ro’yhatdagi elementlani katta yarim va kichik yarimga ajratuvchi qiymat. Listdagi elementlar soni toq bo’lganda, o’rtadagi element median deb olinadi, aks holda o’rtadagi ikki element qo’shilib, yig’indisi ikkiga bo’linadi.

Ishlash tartibi

Eng oson usul albatta ikki array’ni birlashtirib, keyin medianni topish. Tahminan shunday:

Ishlaydi, masalaning javobi topiladi (hatto leetcode ham javobni qabul qiladi). O(log(m + n)) time complexity’ga mos kelyaptimi? Menimcha yo’q, ishlash vaqti O(m + n). Muammolarni ko’rib chiqamiz:

• Array.concat() sekin ishlaydi. Uning ishlash vaqti tahminan O(n) ga teng. U yangi array yaratadi, bu qo’shimcha joy ham egallashini bildiradi. Array.concat() ni Array.push() va spread (…) operatorlariga almashtirsak bo’ladi, shunda ikkinchi array elementlarini birinchi array’ga qo’shib, joy tejaymiz. Lekin baribir ishlash vaqti O(log(m + n)) ga tushib qolmaydi.
• Array.sort() ning ishlash vaqti O (n log n), bu yerda n – birlashtirilgan arrayning uzunligi.

Masalaning qiyinligi ham shunda. O(log(m + n)) tezlikda yechadigan usulni topishimiz kerak.

* * *

Birinchi savol

Biz masalani array’larni birlashtirmasdan turib ham yecha olamizmi?

Medianni topish uchun bizga birlashtirilgan array’ning faqat yarmi, aniqrog’i o’rtasidagi son(lar) kerak bo’ladi. O’sha yarmi elementlari birinchi array’da ham, ikkinchi array’da ham bo’lishi mumkin. Masalan:

const a = [4, 20, 32, 50, 55, 61] // length = 6
const b = [1, 15, 22, 30, 70]     // length = 5
const merged = a.push(...b)       // length = 11

// Birlashtirilgan array:
// [1, 4, 15, 20, 22, 30, 32, 50, 55, 61, 70]
// 30 - median

Yuqoridagi misoldan xulosa qilish mumkinki, birlashtirilgan array’ning yarmiga a array’dan 2 ta, b array’dan 4 ta element kirgan. Ular [4, 20] va [1, 15, 22, 30]

Ikki array’ning elementlar qiymati haqida bilmay turib, biz birlashtirilgan array’ning yarmiga har bir array’dan nechta element kirishini bila olamiz. Ehtimoliy variantlar:

[{1}, {5}], [{2}, {4}], [{3}, {3}], [{4}, {2}], [{5}, {1}], [{6}, {0}]

[{1}, {5}] – birlashtirilgan array’ning yarmida a array’dan 1ta, b array’dan 5ta element borligini ifodalaydi. Variantlar sonini topish formulasi:

Math.ceil((m + n) / 2)

Ikkinchi savol

Birlashtirilgan array’ning yarmiga a va b array’dan nechta element kirishini bilishimiz bizga medianni topishda yordam beradimi?

Ha. Shunchaki a va b array’larni birlashtirilgan array’ning yarmiga kirgan ohirgi elementini topsak kifoya. Shu ikki sondan kattasi median bo’ladi. Misolimizga

Agar qaysidir array’ning birorta ham elementi birlashtirilgan array’ning yarmiga kirmasa, demak median ikkinchi array’ning birlashtirilgan array’ga kirgan ohirgi soni bo’ladi. Masalan:

const a = [3, 6, 9, 13, 15]  // length = 5
const b = [17, 20, 22, 24]   // length = 4

// Birlashtirilgan array:
// [3, 6, 9, 13, 15, 17, 20, 22, 24]
// 15 - median

Uchinchi savol

Agar m + n juft son bo’lsachi?

U holda biz baribir birlashtirilgan array’ning yarmiga kiradigan a va b array’larning ohirgi elementidan kattasini topamiz. Faqat bu safar bizga undan keyingi elementni ham bilish talab etiladi (median’ni topish uchun).

const a = [4, 6, 12]         // length = 3
const b = [5, 7, 9, 15, 17]  // length = 5

// Birlashtirilgan array:
// [4, 5, 6, 7, 9, 12, 15, 17]
// (7 + 9) / 2 = 8 - median

To’rtinchi savol

Agar ehtimoliy variantlar sonini bilar ekanmiz, qaysi variant to’g’riligini qanday topamiz?

Dastlab, ikki array’dan kichigini topib olamiz.

// Array'lar
const a = [4, 20, 32, 50, 55, 61]
const b = [1, 15, 22, 30, 70]

// Ularning uzunligi
const m = a.length
const n = b.length

// Kichik array va katta array
const [small, large] = m < n ? [a, b] : [b, a]

// Kichik array'ning uzunligi x, kattasiniki y
const [x, y] = [small.length, large.length]

// Kichik array'ning bo'luvchi indeksi
const partitionX = Math.floor(x / 2)

// Katta array'ning bo'luvchi indeksi
const partitionY = Math.floor((x + y + 1) / 2) - partitionX

// Kichik array'ning birinchi yarmidagi maksimumi (ikkiga bo'lgandagi ohirgi elementi)
const maxX = small[partitionX - 1]

// Katta array'ning birinchi yarmidagi maksimumi (ikkiga bo'lgandagi ohirgi elementi)
const maxY = large[partitionY - 1]

// Kichik array'ning ikkinchi yarmidagi minimumi
const minX = small[partitionX]

// Katta array'ning ikkinchi yarmidagi minimumi
const minY = large[partitionY]

Yuqoridagilardan kelib chiqadigan bo’lsak:

maxX = 15 (b array kichikroq bo’lgani uchun, uning ikkinchi elementi)
maxY = 50 (b array’dan 2ta element oldik, demak a array’dan 4 ta element olamiz).
minX = 22
minY = 55

Umumiy holda:

const a = [4, 20, 32, 50, 55, 61]
const b = [1, 15, 22, 30, 70]

a array’dan 4 ta element, b array’dan ikkita element oldik. Ularning ichida kattasi – 50. U median bo’la olishini aniqlash uchun, biz ikkiga ajratgan qismlarimiz to’g’ri bo’lganiga ishonch hosil qilishimiz kerak. 50 sonining median bo’lish sharti – ikki array’ning ham chap qismlaridagi qiymatlar o’ng qismlaridagi qiymatlardan kichik (yoki teng) bo’lishi zarur.

maxX <= minY && maxY <= minX

Bizning holatda chap qismdagi 50 o’ng qismdagi 22 dan katta, demak 50 median emas.

Ikkiga ajratishni boshqatdan bajaramiz:

• Agar maxX < minY bo’lsa, partitionX ni bittaga oshiramiz.
• Aks holda, partitionX ni bittaga kamaytiramiz.

Bizdagi misolda maxX (15) < minY (55). partitionX ni bittaga oshirganimizdan keyin:

const a = [4, 20, 32, 50, 55, 61]
const b = [1, 15, 22, 30, 70]

maxX = 22
maxY = 32
minX = 30
minY = 50

maxX <= minY && maxY <= minX shart bajarilmadi (32 < 30).

maxX (22) < minY (50) , partitionX ni bittaga oshiramiz.

const a = [4, 20, 32, 50, 55, 61]
const b = [1, 15, 22, 30, 70]

maxX = 30
maxY = 20
minX = 70
minY = 32

maxX <= minY && maxY <= minX shart bajarildi! median maxX va maxY ichidagi katta son – 30.

Biz masalani yechishga muvaffaq bo’ldik.

Kod