题目

（难）给定两个大小为 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

解答

解法1：
最简单的解法是暴力求解

实际上是希望我们实现下面的算法：

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        both = sorted(nums1 + nums2)    # 合并两个链表
        l = len(both)
        # 计算中位数
        if l % 2 == 0:
            return sum(both[l//2-1:l//2+1]) / 2
        else:
            return both[l//2]

很意外，用时居然超过了绝大多数用户。。
执行用时 : 80 ms, 在Median of Two Sorted Arrays的Python3提交中击败了96.83% 的用户
内存消耗 : 13.3 MB, 在Median of Two Sorted Arrays的Python3提交中击败了65.59% 的用户

如果需要我们实现上面“both = sorted(nums1 + nums2) ”这句话呢？好在两个列表都是有序的，我们只需要写一个函数，用于合并两个有序列表，并使整体有序。时间可达128ms。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        def merge(nums1, nums2):                    # 合并两个有序链表，使结果有序

            result = []                             # 结果数组
            while nums1 or nums2:

                if not nums1:           
                    result += nums2
                    break

                if not nums2:
                    result += nums1
                    break

                if nums1[0] > nums2[0]:
                    result.append(nums2.pop(0))     # 弹出nums2中最小数到result最后
                else:
                    result.append(nums1.pop(0))     # 弹出nums1中最小数到result最后
            return result

        both = merge(nums1, nums2)

        l = len(both)
        if l % 2 == 0:
            return sum(both[l//2-1:l//2+1]) / 2
        else:
            return both[l//2]

上面基本的解答都可以通过，不过，这道题目的本意貌似要用一些其他刁钻技巧，这里直接摘网上的答案吧。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m, n = len(nums1), len(nums2)
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m
        if n == 0:
            raise ValueError

        imin, imax, half_len = 0, m, (m + n + 1) // 2
        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i
            if i < m and nums2[j-1] > nums1[i]:
                # i is too small, must increase it
                imin = i + 1
            elif i > 0 and nums1[i-1] > nums2[j]:
                # i is too big, must decrease it
                imax = i - 1
            else:
                # i is perfect

                if i == 0: max_of_left = nums2[j-1]
                elif j == 0: max_of_left = nums1[i-1]
                else: max_of_left = max(nums1[i-1], nums2[j-1])

                if (m + n) % 2 == 1:
                    return max_of_left

                if i == m: min_of_right = nums2[j]
                elif j == n: min_of_right = nums1[i]
                else: min_of_right = min(nums1[i], nums2[j])

                return (max_of_left + min_of_right) / 2.0

如有疑问，欢迎评论区留言。