4. 寻找两个有序数组的中位数（Python）

Bertha 。 2024-04-19 14:27 74阅读 0赞

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            len_1 = len(nums1)
            len_2 = len(nums2)
            if not nums1 or len(nums1) == 0:
                if len_2 % 2 == 0:
                    return float(nums2[len_2//2] + nums2[len_2//2 - 1]) / 2.0
                else:
                    return nums2[len_2//2]
            if not nums2 or len(nums2) == 0:
                if len_1 % 2 == 0:
                    return float(nums1[len_1//2] + nums1[len_1//2 - 1]) / 2.0
                else:
                    return nums1[len_1//2]
    
            tmp = []
            i = j = 0
            while i < len_1 and j < len_2:
                if nums1[i] <= nums2[j]:
                    tmp.append(nums1[i])
                    i += 1
                else:
                    tmp.append(nums2[j])
                    j += 1
            while i < len_1:
                tmp.append(nums1[i])
                i += 1
            while j < len_2:
                tmp.append(nums2[j])
                j += 1
    
            le = len(tmp)
            if le % 2 == 0:
                return float(tmp[le // 2] + tmp[le // 2 - 1]) / 2.0
            else:
                return tmp[le // 2]