Medián dvou seřazených polí (15. den)

Prohlášení o problému
Jsou-li dána dvě seřazená pole nums1 a nums2 o velikosti ma n, vrátí medián dvou seřazených polí.

Celková složitost doby běhu by měla být O(log (m+n)).

Příklady
Příklad 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

Vysvětlení:sloučené pole =[1,2,3] a medián je 2.

Příklad 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000

Vysvětlení:sloučené pole =[1,2,3,4] a medián je (2 + 3) / 2 =2,5.

Omezení:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

Řešení

var findMedianSortedArrays = function(nums1, nums2) {
    if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1)
    let x = nums1.length
    let y = nums2.length
    let low = 0, high = x
    while(low <= high) {
        const partitionX = (high + low) >> 1
        const partitionY = ((x + y + 1) >> 1) - partitionX

        const maxX = partitionX == 0 ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1]
        const maxY = partitionY == 0 ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1]

        const minX = partitionX == nums1.length ? Number.POSITIVE_INFINITY : nums1[partitionX]
        const minY = partitionY == nums2.length ? Number.POSITIVE_INFINITY : nums2[partitionY ]

        if(maxX <= minY && maxY <= minX) {
            const lowMax = Math.max(maxX, maxY)
            if( (x + y) % 2 == 1)
                return lowMax
            return (lowMax + Math.min(minX, minY)) / 2
        } else if(maxX < minY) {
            low = partitionX + 1
        } else 
            high = partitionX - 1
    }

};

Problém s LeetCode:
https://leetcode.com/problems/median-of-two-sorted-arrays/
Vysvětlení: https://www.youtube.com/watch?v=LPFhl65R7ww

Doufám, že budete Sledovat abyste dostávali pravidelné aktualizace.
Díky, uvidíme se u dalšího příspěvku.