1.题目

原题：

给定两个大小为m和n的有序数组nums1和nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为O(log(m + n))。你可以假设nums1和nums2不会同时为空。

例子：

输入：nums1 = [1, 3]，nums2 = [2]
输出：2.0

2.解析

这道题的解法有很多种，尤其是对于python而言，很多内置函数的使用让求解变得很方便，此题的关键在于满足时间复杂度。为了锻炼算法思维，尽量不借助于python的内置函数实现，主要思路有两种。

• 第一种，将两个数组合并，合并时要满足原来的大小关系，然后根据中位数的寻找方法得到最后的中位数。这种方法的算法复杂度是O(m+n)其实不能满足题目要求，但leetcode上测试是通过的，效率比较低，思路好想。
• 第二种，二分法，题目说算法复杂度是o(log(m+n))，明显提示要用二分法，并且可以用递归的思路做这道题。

3.python代码

3.1 思路1代码

其实就是一个数组的遍历组合，但是要保证数据的排序，所以进行了一个数据大小的比较，思路很清晰。

class Solution:
    def getmid(self, num):
        m = len(num)
        if m % 2 == 0:
            return (num[m // 2 - 1] + num[m // 2]) / 2
        else:
            return num[m//2]

    def findMedianSortedArrays(self, nums1, nums2):
        if nums1 is None:
            return self.getmid(nums2)
        if nums2 is None:
            return self.getmid(nums1)
        i = 0
        j = 0
        num_extend = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] <= nums2[j]:
                num_extend.append(nums1[i])
                i += 1
            elif nums1[i] > nums2[j]:
                num_extend.append(nums2[j])
                j += 1
        if i < len(nums1):
            num_extend.extend(nums1[i:])
        if j < len(nums2):
            num_extend.extend(nums2[j:])
        midnum = self.getmid(num_extend)
        return midnum

3.2 思路2代码

思路2，笔者在写代码的时候趟了几个小坑，记录一下：

• 递归函数需要有明确的函数出口，即使在递归调用的时候，返回值也要用return，否则会造成返回空值的情况。
• log(m+n)复杂度，要求用二分法，二分法在排除前面几个数字后，找第k大的数会变成找第k-i-1大的数，但是如果是排除后面几个数字，找第k大的数仍然不变。

class solution:
    def findMedianSortedArrays(self, nums1, nums2):
        m = len(nums1)
        n = len(nums2)
        k = (m + n) // 2
        if (m + n) % 2 == 0:
            num_mid = (self.findk(nums1, nums2, k) + self.findk(nums1, nums2, k-1))/2
        else:
            num_mid = self.findk(nums1, nums2, k)
        return num_mid

    def findk(self, nums1, nums2, k):
        if not nums1:
            return nums2[k]
        if not nums2:
            return nums1[k]
        i = len(nums1) // 2
        j = len(nums2) // 2
        m1 = nums1[i]
        m2 = nums2[j]
        if i + j < k:
            if m1 < m2:#一定不在nums1的前半部分
                return self.findk(nums1[i+1:], nums2, k-i-1)
            else:
                return self.findk(nums1, nums2[j+1:], k-j-1)
        else:
            if m1 < m2:
                return self.findk(nums1, nums2[:j], k)
            else:
                return self.findk(nums1[:i], nums2, k)