题目

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

示例 1:

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

则中位数是 2.0
示例 2:

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

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

思考

若不考虑复杂度为,显然可以构造一个保序数组,由于 和
是保须的，所以说构造的复杂度为。然后返回



这个题要求了算法复杂度，所以以上的方法是不可以的。
但是我们发现，中位数其实与两个数组的第k小数存在密切关系，我们定义

若则：

若，则与之稍有不同，为两个数字的平均值

但是的算法是啥呢？，下面介绍一种的办法：
首先定义如下变量

m := len(nums1) # m >= 0
n := len(nums2) # n >= 0
1 <= k <= m+n   # 所要找的第k小的数的序号 

然后我们比较和的大小，存在如下三种情况：

, 这种情况说明共计 个元素一定不为问题的解，则，
我们将问题的搜索规模下降了几乎一半

, 这种情况说明共计 个元素一定不为问题的解，则，
我们将问题的搜索规模下降了几乎一半

, 这种情况说明共计 个元素一定不为问题的解，则，
我们将问题的搜索规模下降了几乎一半

这样虽好，但是会存在越界问题

• <越界问题1> 或 为空导致的访问越界<注意不能同时为空>
• <越界问题2> 导致的访问越界
• <越界问题3> 或 导致的访问越界
  针对上述提出的问题，我们在此补全算法，使之越界问题得以考虑：

KthMin(nums1,nums2,k)
    # 越界问题1
    if nums1  is empty:
        return(nums2[k-1])
    if nums2 is empty:
        return(nums1[k-1])
    # 越界问题2
    if k == 1: # 也就是说取最小
        return min(num1[0],nums2[1])
    # 越界问题3
    if k/2-1> = m:
        我们比较 sums1[m-1] 与 sums2[k/2-1]的大小来缩减问题规模
    if k/2-1> = n:
        我们比较 sums2[n-1] 与 sums1[k/2-1]的大小来缩减问题规模
    # 一般情况：
    if nums1[k/2-1] <= nums2[k/2-1]:
        # 缩减问题规模
        return KthMin(nums1[k/2:],nums2,k-k/2)
    if nums1[k/2-1] > nums2[k/2-1]:
        # 缩减问题规模
        return KthMin(nums1,nums2[k-k/2],k-k/2)

代码

class Solution(object):
    def __getKthElement(self, nums1, nums2, k):
        m = nums1.__len__()
        n = nums2.__len__()
        # 越界情况1
        if m == 0:
            return nums2[k - 1]
        elif n == 0:
            return nums1[k - 1]
        # 越界情况2
        elif k == 1:
            return min(nums1[0], nums2[0])
        # 越界情况3
        elif k // 2 - 1 >= m:
            half_k = k // 2 - 1
            if nums1[m - 1] <= nums2[half_k]:
                # return self.__getKthElement([], nums2, k - m)
                return nums2[k - m - 1]
            else:
                return self.__getKthElement(nums1, nums2[half_k + 1:], k - k // 2)
        elif k // 2 - 1 >= n:
            half_k = k // 2 - 1
            if nums1[half_k] <= nums2[n - 1]:
                return self.__getKthElement(nums1[half_k + 1:], nums2, k - k // 2)
            else:
                # return self.__getKthElement(nums1, [], k - n)
                return nums1[k - n - 1]
        # 正常的情况
        else:
            half_k = k // 2 - 1
            if nums1[half_k] <= nums2[half_k]:
                return self.__getKthElement(nums1[half_k + 1:], nums2, k - k // 2)
            else:
                return self.__getKthElement(nums1, nums2[half_k + 1:], k - k // 2)

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = nums1.__len__()
        n = nums2.__len__()
        total_len = m + n
        if (m + n) % 2 == 1:
            return self.__getKthElement(nums1, nums2, (total_len + 1) // 2)
        else:
            return (self.__getKthElement(nums1, nums2, (total_len + 1) // 2) +
                    self.__getKthElement(nums1, nums2, (total_len + 1) // 2 + 1)) / 2.0