寻找两个有序数组的中位数

难度 : 困难

题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

示例
nums1 = [1, 3] nums2 = [2]
则中位数是 2.0
nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

我的解答

class :
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def concat(nums1=[],nums2=[]):
            max_num=[]
            if len(nums1) and len(nums2):
                if nums1[0]<=nums2[0]:
                    max_num.append(nums1[0])
                    max_num+=concat(nums1[1:],nums2)
                else:
                    max_num.append(nums2[0])
                    max_num+=concat(nums1,nums2[1:])
            else:
                if len(nums1)==0:
                    max_num=nums2
                else:
                    max_num=nums1
            return max_num
        mid=float(0)
        conedlist=concat(nums1=nums1,nums2=nums2)
        length=len(conedlist)
        if length>1:
            if length%2==0:
                sth=length//2
                number=(conedlist[sth]+conedlist[sth-1])/2
                mid=float(number)
            else:
                sth=length//2
                mid=float(conedlist[sth])
        elif length==1:
            mid=float(conedlist[0])
        else:
            mid=None
        return mid

寻找两个有序数组的中位数

近期文章

近期评论

标签

热门

文章归档

分类目录

功能