4. 寻找两个正序数组的中位数

题目

4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 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

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

题解

首先，最朴素的思想是直接将两个数组有序合并，然后取中位数，时间复杂度为

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n1 = len(nums1)
        n2 = len(nums2)
        n = n1+n2
        i1 = i2 = 0
        nums3 = []
        for i in range(n):
            if i2 >= n2 or (i1 < n1 and nums1[i1] < nums2[i2]):
                nums3.append(nums1[i1])
                i1 += 1
            else:
                nums3.append(nums2[i2])
                i2 += 1
        if n % 2 == 1:
            return nums3[(n-1)//2]
        else:
            return (nums3[(n+1)//2]+nums3[(n-1)//2])*1.0/2

然后可以进一步优化，因为我们不需要合并后的数组，所以只要让指针的移动数 =(m+n)/2 即可。
这样的话，将空间复杂度从 优化到了

标准答案

其实我们需要的只是中位数，因此前面一大段并没有遍历的必要。
我们可以把这个问题转化为 寻找数组中第k小的数 ，这里的 k=(m+n)/2 。 :::info 对于有序的 数组A 和 数组B，我们要找出其中 第k小的元素 ：

1. 我们首先分别找到A和B的第 k/2 个元素，即 A[k/2] 和 B[k/2]
2. 比较其大小，假设 A[k/2] < B[k/2]，那么说明 第k小的元素 必然不可能在A的前 k/2 个元素中
3. 因此我们可以将A的前k/2个元素 删除掉
4. 接下来的目标是寻找两个数组中 第k/2小的元素 ::: ```python def f(A, B, k): if A == []:

    return B[k-1]
   

   if B == []:

    return A[k-1]
   

   if k == 1:

    return min(A[0], B[0])
   

   i = min(k//2-1, len(A)-1, len(B)-1) if A[i] < B[i]:

    return f(A[i+1:], B, k-i-1)
   

   else:

    return f(A, B[i+1:], k-i-1)
   

class Solution(object): def findMedianSortedArrays(self, nums1, nums2): “”” :type nums1: List[int] :type nums2: List[int] :rtype: float “”” n1 = len(nums1) n2 = len(nums2) n = n1+n2 if n % 2 == 1: return f(nums1, nums2, n//2+1) else: return (f(nums1, nums2, n//2)+f(nums1, nums2, n//2+1))*1.0/2 `` 这样的话，时间复杂度就优化到了 ![](https://cdn.nlark.com/yuque/__latex/7c8c7c65d593ffd8c963fef6d2be90b7.svg#card=math&code=O%28%5Clog%20%28m%2Bn%29%29&height=22&width=117)，但对于此题来说，由于1 <= m + n <= 2000`，因此优化效果不太明显，耗时与上一种方法差不多。