力扣 -- 寻找两个有序数组的中位数 Median of Two Sorted Arrays pyt

题目描述：

中文：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

英文：

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)).

You may assume nums1 and nums2 cannot be both empty.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n1,n2  = len(nums1), len(nums2)
        if n1 > n2:
            nums1, nums2, n1, n2 = nums2, nums1, n2, n1 

        imin, imax, half_len = 0, n1, (n1 + n2 + 1) // 2
        while imin <= imax:
            i = (imin + imax) // 2 
            j = half_len - i 
            if j > 0 and i < n1 and nums1[i] < nums2[j-1]: 
                imin = i + 1
            elif i > 0 and j < n2 and nums1[i-1] > nums2[j]: 
                imax = i - 1
            else:
               
                if i == 0: max_of_left = nums2[j-1] 
                elif j == 0: max_of_left = nums1[i-1]
                else: max_of_left = max(nums1[i-1], nums2[j-1])

                if (n1 + n2) % 2 == 1: 
                    return max_of_left

                if i == n1: min_of_right = nums2[j]
                elif j == n2: min_of_right = nums1[i]
                else: min_of_right = min(nums1[i], nums2[j])

                return (max_of_left + min_of_right) / 2.0

 

 

 

题目来源：力扣

查看更多关于力扣 -- 寻找两个有序数组的中位数 Median of Two Sorted Arrays pyt的详细内容...