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.