题目
给定两个大小分别为 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
- -10^6 <= nums1[i], nums2[i] <= 10^6
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析
解题步骤：
- 如何查找有序数组的中位数
- 如何查找有序数组第k位数
- 优化
如何查找有序数组的中位数
我们来看看如何查找有序数组的中位数：
数组长度为奇数
当数组长度为奇数n时，有一位中位数，为：(n + 1) / 2
数组长度为偶数
当数组长度为偶数n时，有两位中位数，分别为：n / 2 和 (n + 2) / 2
所以题目就变成了：
- 当m + n为奇数时，查找第 (m + n + 1) / 2 位数
- 当m + n为偶数时，查找第 (m + n) / 2 和 (m + n + 2) / 2 位数
如何查找有序数组第k位数
我们定义两个变量i和j，i代表数组nums1的下标，j代表数组nums2的下标，初始值都为0
下面我们只需要解决两个问题：
- 如何移动边界i和j
- 判定查找到目标值
如何移动边界i和j
边界
- 比较nums1[i]和nums2[j]值的大小
- 当nums1[i] <= nums2[j]时，此时nums1[i]肯定不是第k位数，所以此时需要移动边界i，最简单的方式就是移动一位i++
- 当nums1[i] > nums2[j]时，此时nums2[j]肯定不是第k位数，所以此时需要移动边界j，最简单的方式就是移动一位j++
- 经过步骤1，边界已经移动了一位，所以需要查找目标值的位数也需要改变k--
- 循环继续下一次查找
判定查找到目标值
- 当i >= nums1的长度时，此时只用查找nums2即可，目标值下标为：j + k - 1
- 当j >= nums2的长度时，此时只用查找nums1即可，目标值下标为：i + k - 1
- 当k == 1时，此时需要比较nums1[i]和nums2[j]值的大小
- 当nums1[i] <= nums2[j]时，此时目标值为nums1[i]
- 当nums1[i] > nums2[j]时，此时目标值为nums2[j]
把以上思想整理成go代码如下：
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums1Len := len(nums1)
nums2Len := len(nums2)
// 特殊判断
if nums1Len + nums2Len == 0 {
return 0.0
}
if (nums1Len + nums2Len) % 2 == 0 {
// 数组长度为偶数，需要查找两个中位数
return float64(findK(nums1, 0, nums1Len, nums2, 0, nums2Len, (nums1Len + nums2Len) / 2) + findK(nums1, 0, nums1Len, nums2, 0, nums2Len, (nums1Len + nums2Len + 2) / 2)) / 2.0
} else {
// 数组长度为奇数，需要查找一位中位数
return float64(findK(nums1, 0, nums1Len, nums2, 0, nums2Len, (nums1Len + nums2Len + 1) / 2))
}
}
func findK(nums1 []int, i int, nums1Len int, nums2 []int, j int, nums2Len int, k int) int {
// 判断左边界是否越界
if i >= nums1Len {
return nums2[j + k - 1]
}
// 判断右边界是否越界
if j >= nums2Len {
return nums1[i + k - 1]
}
// 判断第一位是否就是目标值
if k == 1 {
if nums1[i] <= nums2[j] {
return nums1[i]
} else {
return nums2[j]
}
}
// 判断如何移动边界
if nums1[i] <= nums2[j] {
i++
} else {
j++
}
k--
return findK(nums1, i, nums1Len, nums2, j, nums2Len, k)
} 优化
题目给出了两个重要信息：
- 正序（从小到大）数组
- 时间复杂度应该为 O(log (m+n))
正序 + 时间复杂度为log，基本就可以联想到二分法了
以上代码中，我们可以优化的地方是移动边界的逻辑：每次简单的移动一位 -> 每次移动 k / 2 位，减少循环查找次数
优化代码：
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums1Len := len(nums1)
nums2Len := len(nums2)
// 特殊判断
if nums1Len + nums2Len == 0 {
return 0.0
}
if (nums1Len + nums2Len) % 2 == 0 {
// 数组长度为偶数，需要查找两个中位数
return float64(findK(nums1, 0, nums1Len, nums2, 0, nums2Len, (nums1Len + nums2Len) / 2) + findK(nums1, 0, nums1Len, nums2, 0, nums2Len, (nums1Len + nums2Len + 2) / 2)) / 2.0
} else {
// 数组长度为奇数，需要查找一个中位数
return float64(findK(nums1, 0, nums1Len, nums2, 0, nums2Len, (nums1Len + nums2Len + 1) / 2))
}
}
func findK(nums1 []int, i int, nums1Len int, nums2 []int, j int, nums2Len int, k int) int {
// 判断左边界是否越界
if i >= nums1Len {
return nums2[j + k - 1]
}
// 判断右边界是否越界
if j >= nums2Len {
return nums1[i + k - 1]
}
// 判断第一位是否就是目标值
if k == 1 {
if nums1[i] <= nums2[j] {
return nums1[i]
} else {
return nums2[j]
}
}
// 优化移动边界逻辑，每次移动 k / 2
num1 := math.MaxInt
if i + k/2 - 1 < nums1Len {
num1 = nums1[i + k/2 - 1]
}
num2 := math.MaxInt
if j + k/2 - 1 < nums2Len {
num2 = nums2[j + k/2 - 1]
}
if num1 <= num2 {
i = i + k/2
} else {
j = j + k/2
}
return findK(nums1, i, nums1Len, nums2, j, nums2Len, k - k/2)
}