1. 题目描述
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
提示:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
2. 分析
核心思路:二分查找收缩
本题要求两个升序数组的中位数,先转化为求解通用问题:两个升序数组的第k小元素。
而后再根据元素个数奇偶,求解中位数。
3. 代码
3.1. 简单方案
func findKthElement(nums1 []int, nums2 []int, k int) int {
if len(nums1) == 0 {
return nums2[k-1]
}
if len(nums2) == 0 {
return nums1[k-1]
}
if k == 1 {
if nums1[0] < nums2[0] {
return nums1[0]
}
return nums2[0]
}
if nums1[0] < nums2[0] {
return findKthElement(nums1[1:], nums2, k-1)
}
return findKthElement(nums1, nums2[1:], k-1)
}
上述方案求解两个升序数组的第k小元素,基本思路是利用合并两个升序数组,找到第k小。时间复杂度O(m+n)。不符合题意。
3.2. 二分查找
func findKthElement(nums1 []int, nums2 []int, k int) int {
m, n := len(nums1), len(nums2)
// 边界条件:如果一个数组为空,直接在另一个数组中查找第 k 小元素
if m == 0 {
return nums2[k-1]
}
if n == 0 {
return nums1[k-1]
}
// 边界条件:如果 k 为 1,直接返回两个数组中的最小值
if k == 1 {
if nums1[0] < nums2[0] {
return nums1[0]
}
return nums2[0]
}
// 找到两个数组的第 k/2 个元素位置(注意索引偏移)
// 如果数组长度不足 k/2,取最大长度
idx1 := min(m, k>>1) - 1
idx2 := min(n, k>>1) - 1
// 比较两个数组的第 k/2 个元素
if nums1[idx1] < nums2[idx2] {
// nums1 收缩
return findKthElement(nums1[idx1+1:], nums2, k-idx1-1)
} else {
// nums2 收缩
return findKthElement(nums1, nums2[idx2+1:], k-idx2-1)
}
}
func min(nums1, nums2 int) int {
if nums1 < nums2 {
return nums1
}
return nums2
}
最后,再根据奇偶性,求解中位数。
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
mid := (m + n) / 2
if (m+n)&1 == 1 {
// 奇数个,取中间值 注意索引偏移:[1,2,3] mid=1 中间值是第二个元素
return float64(findKthElement(nums1, nums2, mid+1))
}
// 偶数个,取中间两个值
return float64(findKthElement(nums1, nums2, mid)+findKthElement(nums1, nums2, mid+1)) / 2
}
评论