4. 寻找两个有序数组的中位数（困难）

• 难度: 困难
• 考察: 数组
• 来源: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
• 题解: https://mp.weixin.qq.com/s/FBlH7o-ssj_iMEPLcvsY2w

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

思路

题目说的是给两个排好序的数组，让你求出这两个数组中所有元素按从小到大排列，排在中间的元素，时间复杂度也是有要求的，O(log(m + n))，m 和 n 分别是这两个数组的长度。

这里提到了时间复杂度为 O(log(m+n)) ，很容易想到的就是二分查找，所以现在要做的就是在两个排序数组中进行二分查找。

具体思路如下，将问题 转化为在两个数组中找第 K 个小的数 。

求中位数，其实就是求第 k 小数的一种特殊情况。

首先在两个数组中分别找出第 k/2 大的数，再比较这两个第 k/2 大的数，这里假设两个数组为 A ，B。

那么比较结果会有下面几种情况：

A[k/2] = B[k/2],那么第 k 大的数就是 A[k/2]

A[k/2] > B[k/2],那么第 k 大的数肯定在 A[0:k/2+1] 和 B[k/2:] 中，这样就将原来的所有数的总和减少到一半了，再在这个范围里面找第 k/2 大的数即可，这样也达到了二分查找的区别了。

A[k/2] < B[k/2]，那么第 k 大的数肯定在 B[0:k/2+1]和 A[k/2:] 中，同理在这个范围找第 k/2 大的数就可以了。

关键点

二分查找

复杂度

• 时间复杂度：O(log(m + n))

时间复杂度：每进行一次循环，减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k = (m+n) / 2，所以最终的复杂也就是 O(log(m+n）。

• 空间复杂度：O(1)

虽然用到了递归，但是可以看到这个递归属于尾递归，所以编译器不需要不停地堆栈，所以空间复杂度为 O(1)。

代码

递归去掉不需要的部分

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	l1 := len(nums1)
	l2 := len(nums2)
	left := (l1 + l2 + 1) / 2
	right := (l1 + l2 + 2) / 2
	if left == right {
		return float64(get(nums1, 0, l1-1, nums2, 0, l2-1, left))
	}
	return float64(get(nums1, 0, l1-1, nums2, 0, l2-1, left)+get(nums1, 0, l1-1, nums2, 0, l2-1, right)) / 2
}

func get(nums1 []int, s1, e1 int, nums2 []int, s2, e2, k int) int {
	l1 := e1 - s1 + 1
	l2 := e2 - s2 + 1
	// 如果 nums1 和 nums2 有一个空了，那肯定是nums1
	if l1 > l2 {
		return get(nums2, s2, e2, nums1, s1, e1, k)
	}
	if l1 == 0 {
		return nums2[s2+k-1]
	}
	if k == 1 {
		return minNum(nums1[s1], nums2[s2])
	}

	x1 := s1 + minNum(l1, k/2) - 1
	x2 := s2 + minNum(l2, k/2) - 1

	if nums1[x1] > nums2[x2] {
		return get(nums1, s1, e1, nums2, x2+1, e2, k-(x2-s2+1))
	}
	return get(nums1, x1+1, e1, nums2, s2, e2, k-(x1-s1+1))
}

func minNum(n1, n2 int) int {
	if n1 < n2 {
		return n1
	} else {
		return n2
	}
}

笨办法，每次循环去掉不需要的部分

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    var firstIndex, secondIndex int
    if (len(nums1) + len(nums2))%2 == 0 {
        firstIndex = (len(nums1) + len(nums2))/2 - 1
        secondIndex = firstIndex +1
    }else{
        firstIndex = (len(nums1) + len(nums2))/2
        secondIndex = firstIndex
    }

    for {
        fmt.Printf("start fi=%d, si=%d, %v, %v \n",firstIndex, secondIndex, nums1,nums2)

        // 其中一个为空，取另一个数组计算并返回
        if len(nums1) == 0 {
            return avg(nums2[firstIndex], nums2[secondIndex])
        }
        if len(nums2) == 0 {
            return avg(nums1[firstIndex], nums1[secondIndex])
        }

        // 不需要的数据已经去除完毕
        if firstIndex == 0 {
            if firstIndex == secondIndex {
                return float64(minNum(nums1[0], nums2[0]))
            }
            if len(nums1) >= 2 && nums1[0] <= nums2[0]{
                return avg(nums1[0], minNum(nums1[1], nums2[0]))
            }
            if len(nums2) >= 2 && nums2[0] <= nums1[0]{
                return avg(nums2[0], minNum(nums2[1], nums1[0]))
            }
            return avg(nums1[0], nums2[0])
        }


        curIndex := firstIndex / 2 - 1
        if curIndex < 0{
            curIndex = 0
        }
        if len(nums1) - 1 < curIndex {
            curIndex = len(nums1) - 1
        }
        if len(nums2) - 1 < curIndex {
            curIndex = len(nums2) - 1
        }
        firstIndex -= curIndex + 1
        secondIndex -= curIndex + 1

        if nums1[curIndex] > nums2[curIndex]{
            nums2 = nums2[curIndex+1:]
        }else{
            nums1 = nums1[curIndex+1:]
        }
        fmt.Printf("end ci=%d, fi=%d, si=%d, %v, %v \n\n",curIndex,firstIndex, secondIndex, nums1,nums2)
    }
    return 0
}

func minNum(num1, num2 int) int{
    if num1 < num2{
        return num1
    }else{
        return num2
    }
}

func avg(num1, num2 int) float64{
    return (float64(num1) + float64(num2))/2
}