题目 给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2
输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
解法: 这题麻烦在想清楚自己切分的中位数是在切分线的左侧还是右侧。 另外就是有些边界条件比较麻烦,我是调试出来的。 核心思想是二分查找法+切分数组:
func Min(a int, b int) int {
if a < b {
return a
}
return b
}
func Max(a int, b int) int {
if a > b {
return a
}
return b
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
if len(nums1) > len(nums2) {
return findMedianSortedArrays(nums2, nums1)
}
leftA := 0
rightA := len(nums1) - 1
midA, midB, k := 0, 0, (len(nums1) + len(nums2)) >> 1
for {
midA = (leftA + rightA + 1) >> 1
midB = k - midA
if midA > 0 && nums1[midA-1] > nums2[midB] {
rightA = midA-1
} else if midA != len(nums1) && nums1[midA] < nums2[midB-1] {
leftA = midA+1
} else {
break
}
}
left, right := 0, 0
if midA < 0 || midA >= len(nums1) {
right = nums2[midB]
} else if midB < 0 || midB >= len(nums2) {
right = nums1[midA]
} else {
right = Min(nums1[midA], nums2[midB])
}
if (len(nums1) + len(nums2)) % 2 != 0 {
return float64(right)
}
if midA == 0 {
left = nums2[midB-1]
} else if midB == 0 {
left = nums1[midA-1]
} else {
left = Max(nums1[midA-1], nums2[midB-1])
}
return float64(left + right) / 2
}
|