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

发布时间：2020-12-20 10:41:11 所属栏目：Python 来源：网络整理

导读：题目描述：中文：给定两个大小为 m 和 n 的有序数组?nums1 和?nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为?O(log(m + n))。你可以假设?nums1?和?nums2?不会同时为空。英文： There are two sorted arrays nums1 and nums2 of s

题目描述：

中文：

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

        imin,imax,half_len = 0,(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

题目来源：力扣

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!