【leedcode】0004. 两个有序数组的中位数

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

方法一：时间复杂度O(m+n)

def Medianof2Arrays(num1,num2):
    
    n1,n2 = len(num1),len(num2)
    res = [0]*(n1+n2)
    n,i,j = 0,0,0
    
    while n < n1+n2:
        if i < n1 and j < n2:
            if num1[i] < num2[j]:
                res[n] = num1[i]
                i += 1
            else:
                res[n] = num2[j]
                j += 1
        elif i >= n1 and j < n2:
            res[n] = num2[j]
            j += 1
        elif i < n1 and j >= n2:
            res[n] = num1[i]
            i += 1
        n += 1

    if (n1+n2)%2:
        return res[(n1+n2)//2]
    else:
        return (res[(n1+n2)//2]+res[(n1+n2)//2-1])/2

nums1,nums2 = [1,3],[2]
print(Medianof2Arrays(nums1,nums2))

print()

nums1,nums2 = [1,2],[3,4]
print(Medianof2Arrays(nums1,nums2))

**方法二： **

def Medianof2Arrays(num1,num2):

    n1,n2 = len(num1),len(num2)
    if(n1>n2):
        num1,num2 = num2,num1
        n1,n2 = n2,n1
    try: Max = (num1[-1],num2[-1]) + 1
    except: Max = num2[-1] + 1
    try: Min = (num1[0],num2[0]) - 1
    except: Min = num2[0] - 1
    
    lo,hi = 0,2*n1
    while lo<=hi:
        c1 = (lo+hi)//2
        c2 = n1+n2-c1
        L1 = Min if c1==0 else num1[(c1-1)//2]
        R1 = Max if c1==2*n1 else num1[c1//2]
        L2 = Min if c2==0 else num2[(c2-1)//2]
        R2 = Max if c2==2*n2 else num2[c2//2]
        if L1>R2: hi = c1-1
        elif L2>R1: lo = c1+1
        else: break

    return (max(L1,L2)+min(R1,R2))/2

nums1,nums2 = [1,3],[2]
print(Medianof2Arrays(nums1,nums2))

print()

nums1,nums2 = [1,2],[3,4]
print(Medianof2Arrays(nums1,nums2))

方法三：直接用内置函数操作

def Medianof2Arrays(num1,num2):
    res = num1[:]
    res.extend(num2)
    res.sort()
    if (n:=len(res))%2:
        return res[n//2]
    else:
        return (res[n//2]+res[n//2-1])/2

nums1,nums2 = [1,3],[2]
print(Medianof2Arrays(nums1,nums2))

print()

nums1,nums2 = [1,2],[3,4]
print(Medianof2Arrays(nums1,nums2))

欢迎加入“派森特给站”社区！https://bbs.csdn.net/forums/PythonTogether

https://bbs.csdn.net/forums/PythonTogether