问题描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

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

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

类似于归并两个有序数组，但是不会开辟一个长度为 m + n 的数组保存每个元素，而是只保存遍历到的最后两个元素，当遍历到数组的中间位置时，停止遍历，然后计算中位数，返回。

需要注意：当两个数组的长度之和为奇数时，中位数是中间的那个元素，否则是中间的两个元素的平均数。

Python 实现

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if not nums1 and not nums2:
            return 0.

        i = j = 0
        cur_index = 0
        total_length = len(nums1) + len(nums2)
        end = total_length / 2
        prev_element = mid_element = None

        while i < len(nums1) and j < len(nums2):
            prev_element = mid_element
            if nums1[i] <= nums2[j]:
                mid_element = nums1[i]
                i = i + 1
            else:
                mid_element = nums2[j]
                j = j + 1

            if cur_index == end:
                if total_length % 2:
                    return mid_element / 1.0
                return (prev_element + mid_element) / 2.0

            cur_index = cur_index + 1

        remaining, index = (nums2, j) if i >= len(nums1) else (nums1, i)
        while index < len(remaining):
            prev_element = mid_element
            mid_element = remaining[index]
            index = index + 1

            if cur_index == end:
                if total_length % 2:
                    return mid_element / 1.0
                return (prev_element + mid_element) / 2.0

            cur_index = cur_index + 1