博客

题目描述

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

思路

将给定的两个有序数组，使用归并排序到同一个数组，再求中位数就好啦

代码

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m=len(nums1)
        n=len(nums2)
        i=0
        j=0
        a=[]
        while i<m and j<n:
            if nums1[i]<nums2[j]:
               a.append(nums1[i])
               i+=1
            else:
               a.append(nums2[j])
               j+=1
        if i==m:
            for each in range(j,n):
                a.append(nums2[each])
        
        if j==n:
             for each in range(i,m):
                 a.append(nums1[each])
        if (m+n)%2==0:
             return((a[(m+n)//2-1]+a[(m+n)//2])/2) 
        else:
             return(a[(m+n+1)//2-1])