[Leetcode]Median of Two Sorted Arrays

àì夳堔傛蜴生んèń 2022-06-09 03:59 212阅读 0赞

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:  
nums1 = \[1, 3\]  
nums2 = \[2\]

The median is 2.0  
Example 2:  
nums1 = \[1, 2\]  
nums2 = \[3, 4\]

The median is (2 + 3)/2 = 2.5  
给出两个已经排序好的数组，算出两个数组的中位数  
首先我的想法是先合并两个数组，然后根据个数，得到中位数的下表求出中位数

class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            median = 0
            nums = nums1 + nums2
    
            m = len(nums)
            if(m%2==0):
                median=(nums[m/2]+nums[m/2+1])/2.0
            else:
                median=nums[m//2+1]
            return(median)

虽然结果是对的，但是题目要求时间复杂度控制在O(log(m+n)),显然以上做法时间复杂度为O(m+n)。  
然后网上看了别人用二分的思想

class Solution:
        def findKthSortedArrays(self, A, B, k):
            if len(A) < len(B):
                tmp = A
                A = B
                B = tmp
            if len(B) == 0:
                return A[k - 1]
            if k == 1:
                return min(A[0], B[0])
    
            pb = min(k / 2, len(B))
            pa = k - pb
            if A[pa - 1] > B[pb - 1]:
                return self.findKthSortedArrays(A, B[pb:], k - pb)
            elif A[pa - 1] < B[pb - 1]:
                return self.findKthSortedArrays(A[pa:], B, k - pa)
            else:
                return A[pa - 1]
    
        # @return a float
        def findMedianSortedArrays(self, A, B):
            if (len(A) + len(B)) % 2 == 1:
                return self.findKthSortedArrays(A, B, (len(A) + len(B)) / 2 + 1)
            else:
                return (self.findKthSortedArrays(A, B, (len(A) + len(B)) / 2) +
                    self.findKthSortedArrays(A, B, (len(A) + len(B)) / 2 + 1)) / 2.0