给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
思路：
看到这道题的第一个思路是使用类似归并排序的方式，将两个数组合并成一个有序数组，在对这个有序数组求中位数。
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums := newNums(nums1, nums2)
if len(nums)%2 == 1 {
return float64(nums[len(nums)/2])
} else {
return float64(nums[len(nums)/2]+nums[len(nums)/2-1]) / 2.0
}
}
func newNums(nums1, nums2 []int) []int {
newnums := make([]int, len(nums1)+len(nums2))
for i, j, k := 0, 0, 0; i < len(nums1) || j < len(nums2); k++ {
//如果有一个数组被读取完，则将另一个数组剩下的数字加入新创建数组的末尾
if i == len(nums1) {
for ; j < len(nums2); j, k = j+1, k+1 {
newnums[k] = nums2[j]
}
return newnums
}
if j == len(nums2) {
for ; i < len(nums1); i, k = i+1, k+1 {
newnums[k] = nums1[i]
}
return newnums
}
//比较两个数组将较小的加入新数组当中，并将指针的后移
if nums1[i] < nums2[j] {
newnums[k] = nums1[i]
i++
} else {
newnums[k] = nums2[j]
j++
}
}
return newnums
}
但是使用这个方法合并数组至少需要min(M,N)次的比较，所以算法的时间复杂度为O(m+n)，并不符合题目的要求。
转化思路：
看到O(log)的复杂度，很容易就会想到二分查找，但是由于数据分布在两个数组这就为我们的二分查找带来了困难。我们首先想到中位数本质是一个分割，一侧的数都小于该数，另一侧则都大于该数，所以我们可以从两边采取取总数一半的策略。具体步骤分析如下：
package conf
//分割线左边多一个数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
//1.判断是奇数还是偶数，奇数返回分割线左边的第一个数，偶数返回分割线两侧的平均数
var sum int
sum = len(nums1) + len(nums2)
if sum%2 == 1 {
//2，在奇数内运行分割线的寻找函数
return float64(getDivLine(nums1, nums2, sum/2+1))
} else {
//3，在偶数部分运行分割线的查找函数
return float64(getDivLine(nums1, nums2, sum/2+1)+getDivLine(nums1, nums2, sum/2)) / 2.0
}
}
func getDivLine(nums1, nums2 []int, need int) int {
index1, index2 := 0, 0
for {
//1.如果任意数组放入左边的量已经等于数组大小，则返回另一数组已返回左边的大小，加需求数目。如果need==1，则返回两数组分割线左边较小的数值。
if index1 == len(nums1) {
return nums2[index2+need-1]
}
if index2 == len(nums2) {
return nums1[index1+need-1]
}
if need == 1 {
return min(nums1[index1], nums2[index2])
}
//2.将小于分割线所需要的数进行均分，得到对应两个数组所需要的小于分割线的数量
half := need / 2
//3.分别比较两数组需要的数和数组长度的比较，如果长与数组长度，则返回数组的最后一个值
newindex1 := min(index1+half, len(nums1)) - 1
newindex2 := min(index2+half, len(nums2)) - 1
pivot1, pivot2 := nums1[newindex1], nums2[newindex2]
//4，比较两个数组分别分割后的大小，将较小的数组放入分割线的左侧，同时减少需求数的数
if pivot1 <= pivot2 {
need -= newindex1 - index1 + 1
index1 = newindex1 + 1
} else {
need -= newindex2 - index2 + 1
index2 = newindex2 + 1
}
}
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
有疑问加站长微信联系（非本文作者）
