寻找两个正序数组的中位数 - 二分 1
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
n, m := len(nums1), len(nums2)
left := (n + m + 1) >> 1
right := (n + m + 2) >> 1
if left == right { // odd
return float64(getKth(nums1, nums2, left))
}
// even
return (float64(getKth(nums1, nums2, left)) + float64(getKth(nums1, nums2, right))) / 2
}
// 获取第 k 小的数
func getKth(nums1, nums2 []int, k int) int {
len1, len2 := len(nums1), len(nums2)
//让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
if len1 > len2 {
return getKth(nums2, nums1, k)
}
if len1 == 0 {
return nums2[k - 1]
}
if k == 1 {
return min(nums1[0], nums2[0])
}
idx1 := min(len1, k >> 1)
idx2 := min(len2, k >> 1)
if nums1[idx1 - 1] > nums2[idx2 - 1] {
return getKth(nums1, nums2[idx2:], k - idx2)
}
return getKth(nums1[idx1:], nums2, k - idx1)
}
寻找两个正序数组的中位数 - 二分 2
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
n, m := len(nums1), len(nums2)
if m < n { // 保证 nums1 不长于 nums2
n, m = m, n
nums1, nums2 = nums2, nums1
}
iMin, iMax := 0, n
for iMin <= iMax {
i := iMin + (iMax - iMin) >> 1
// i + j = n - i + m - j
j := (n + m + 1) >> 1 - i
if j > 0 && i < n && nums2[j - 1] > nums1[i] { // i 需要增大
iMin = i + 1
} else if i > 0 && j < m && nums1[i - 1] > nums2[j] { // i 需要减小
iMax = i - 1
} else {
maxLeft := 0
if i == 0 {
maxLeft = nums2[j - 1]
} else if j == 0 {
maxLeft = nums1[i - 1]
} else {
maxLeft = max(nums1[i - 1], nums2[j - 1])
}
if (n + m) & 1 == 1 { // odd
return float64(maxLeft)
}
minRight := 0
if i == n {
minRight = nums2[j]
} else if j == m {
minRight = nums1[i]
} else {
minRight = min(nums1[i], nums2[j])
}
// even
return (float64(maxLeft) + float64(minRight)) / 2
}
}
return 0
}