难度:困难

知识点:数组、二分查找、分治算法

地址: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

给定两个大小为 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
In [6]:
class Solution:

    def findMedianSortedArrays(self, nums1: list, nums2: list) -> float:
        '''
        执行用时 : 104 ms, 在Median of Two Sorted Arrays的Python3提交中击败了62.78% 的用户
        内存消耗 : 13.4 MB, 在Median of Two Sorted Arrays的Python3提交中击败了47.77% 的用户
        
        因为是有序列表,同时按照索引比较两个数组的数,重组一个有序的新列表,长度大的列表比较剩下的部分可以直接拼接到新数组中
        '''

        nums = []
        i, j = 0, 0
        while i < len(nums1) and j < len(nums2):
            x = nums1[i]
            y = nums2[j]
            if x < y:
                nums.append(x)
                i += 1
            else:
                nums.append(y)
                j += 1
        if i < len(nums1) and j >= len(nums2):
            nums.extend(nums1[i:])
        elif i >= len(nums1) and j < len(nums2):
            nums.extend(nums2[j:])
        
        if len(nums) % 2:
            return nums[len(nums) // 2]
        else:
            mid = len(nums) // 2
            return (nums[mid] + nums[mid - 1]) / 2
            

        
s = Solution()
assert s.findMedianSortedArrays([1, 3], [2]) == 2.0
assert s.findMedianSortedArrays([1, 2], [3, 4]) == 2.5