WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

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)) bölsin.

Misol:

Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Tuşuntiriş: birlaştirilgan array = [1,2,3] va median = 2.

Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Tuşuntiriş:** birlaştirilgan array = [1,2,3,4] va median (2 + 3) / 2 = 2.5.

Median - tartiblangan array yoki röyhatdagi elementlani katta yarim va kiçik yarimga ajratuvçi qiymat. Listdagi elementlar soni toq bölganda, örtadagi element median deb olinadi, aks holda örtadagi ikki element qöşilib, yiğindisi ikkiga bölinadi.

Işlaş tartibi

Eng oson usul albatta ikki array'ni birlaştirib, keyin medianni topiş. Tahminan şunday:

Işlaydi, masalaning javobi topiladi (hatto leetcode ham javobni qabul qiladi). O(log(m + n)) time complexity'ga mos kelyaptimi? Menimça yöq, işlaş vaqti O(m + n). Muammolarni körib çiqamiz:

  • Array.concat() sekin işlaydi. Uning işlaş vaqti tahminan O(n) ga teng. U yangi array yaratadi, bu qöşimça joy ham egallaşini bildiradi. Array.concat() ni Array.push() va spread (...) operatorlariga almaştirsak böladi, şunda ikkinçi array elementlarini birinçi array'ga qöşib, joy tejaymiz. Lekin baribir işlaş vaqti O(log(m + n)) ga tuşib qolmaydi.
  • Array.sort() ning işlaş vaqti O (n log n), bu yerda n - birlaştirilgan arrayning uzunligi.

Masalaning qiyinligi ham şunda. O(log(m + n)) tezlikda yeçadigan usulni topişimiz kerak.


Birinçi savol

Biz masalani array'larni birlaştirmasdan turib ham yeça olamizmi?

Medianni topiş uçun bizga birlaştirilgan array'ning faqat yarmi, aniqroği örtasidagi son(lar) kerak böladi. Öşa yarmi elementlari birinçi array'da ham, ikkinçi array'da ham bölişi 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

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

Yuqoridagi misoldan xulosa qiliş mumkinki, birlaştirilgan 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 birlaştirilgan array'ning yarmiga har bir array'dan neçta element kirişini bila olamiz. Ehtimoliy variantlar:

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

[{1}, {5}] - birlaştirilgan array'ning yarmida a array'dan 1ta, b array'dan 5ta element borligini ifodalaydi. Variantlar sonini topiş formulasi:

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

Ikkinçi savol

Birlaştirilgan array'ning yarmiga a va b array'dan neçta element kirişini bilişimiz bizga medianni topişda yordam beradimi?

Ha. Şunçaki a va b array'larni birlaştirilgan array'ning yarmiga kirgan ohirgi elementini topsak kifoya. Şu ikki sondan kattasi median böladi. Misolimizga

Agar qaysidir array'ning birorta ham elementi birlaştirilgan array'ning yarmiga kirmasa, demak median ikkinçi array'ning birlaştirilgan array'ga kirgan ohirgi soni böladi. Masalan:

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

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

Uçinçi savol

Agar m + n juft son bölsaçi?

U holda biz baribir birlaştirilgan array'ning yarmiga kiradigan a va b array'larning ohirgi elementidan kattasini topamiz. Faqat bu safar bizga undan keyingi elementni ham biliş talab etiladi (median'ni topiş uçun).

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

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

Törtinçi savol

Agar ehtimoliy variantlar sonini bilar ekanmiz, qaysi variant töğriligini qanday topamiz?

Dastlab, ikki array'dan kiçigini 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

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

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

// Kiçik array'ning böluvçi indeksi
const partitionX = Math.floor(x / 2)

// Katta array'ning böluvçi indeksi
const partitionY = Math.floor((x + y + 1) / 2) - partitionX

// Kiçik array'ning birinçi yarmidagi maksimumi (ikkiga bölgandagi ohirgi elementi)
const maxX = small[partitionX - 1]

// Katta array'ning birinçi yarmidagi maksimumi (ikkiga bölgandagi ohirgi elementi)
const maxY = large[partitionY - 1]

// Kiçik array'ning ikkinçi yarmidagi minimumi
const minX = small[partitionX]

// Katta array'ning ikkinçi yarmidagi minimumi
const minY = large[partitionY]

Yuqoridagilardan kelib çiqadigan bölsak:

maxX = 15 (b array kiçikroq bölgani uçun, uning ikkinçi 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 içida kattasi - 50. U median böla olişini aniqlaş uçun, biz ikkiga ajratgan qismlarimiz töğri bölganiga işonç hosil qilişimiz kerak. 50 sonining median böliş şarti - ikki array'ning ham çap qismlaridagi qiymatlar öng qismlaridagi qiymatlardan kiçik (yoki teng) bölişi zarur.

maxX &lt;= minY &amp;&amp; maxY &lt;= minX

Bizning holatda çap qismdagi 50 öng qismdagi 22 dan katta, demak 50 median emas.

Ikkiga ajratişni boşqatdan bajaramiz:

  • Agar maxX &lt; minY bölsa, partitionX ni bittaga oşiramiz.
  • Aks holda, partitionX ni bittaga kamaytiramiz.

Bizdagi misolda maxX (15) < minY (55). partitionX ni bittaga oşirganimizdan 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 &lt;= minY &amp;&amp; maxY &lt;= minX şart bajarilmadi (32 < 30).

maxX (22) &lt; minY (50) , partitionX ni bittaga oşiramiz.

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

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

maxX &lt;= minY &amp;&amp; maxY &lt;= minX şart bajarildi! median maxX va maxY içidagi katta son - 30.

Biz masalani yeçişga muvaffaq böldik.

Kod