Untitled

mail@pastecode.io avatar
unknown
plain_text
9 months ago
2.3 kB
3
Indexable
Never
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def updateTarget(k):
            return k-k/2
        # initilization
        offset_1 = 0
        offset_2 = 0
        total_length = len(nums1)+len(nums2)
        # 偶数长度最后处理
        
        # 问题实际上转化为第k小问题
        k = total_length//2+total_length%2
        
        while(True):
            p1 = offset_1+k//2-1
            p2 = offset_2+k//2-1
            #print(p1,p2,k)
            # 检查越界,更新p1,p2
            if len(nums1)==0 or len(nums2)==0:
                break
            elif not p1<len(nums1):
                p1 = len(nums1)-1
            elif not p2<len(nums2):
                p2 = len(nums2)-1
            # 此时比nums1[p1]小的数至多有k-2个
            if nums1[p1]<=nums2[p2]:
                k = k- (p1-offset_1+1)
                offset_1 = p1+1#新的左界限从p1+1开始
            # 同理排除nums2[p2]
            else:
                k = k - (p2-offset_2+1)
                offset_2 = p2+1
            
            if k==1 or offset_1 ==len(nums1) or offset_2==len(nums2):
                break
        #print(offset_1,offset_2,k)
        if total_length%2 ==1:
            if offset_1 == len(nums1):
                return nums2[offset_2+k-1]
            elif offset_2==len(nums2):
                return nums1[offset_1+k-1]
            if k==1:return min(nums1[offset_1],nums2[offset_2])
        else:
            if offset_1==len(nums1):
                return (nums2[offset_2+k-1]+nums2[offset_2+k])/2
            elif offset_2==len(nums2):
                return (nums1[offset_1+k-1]+nums1[offset_1+k])/2
            elif k==1:
                n1 = -1
                n2 = -1
                if nums1[offset_1]<=nums2[offset_2]:
                    n1 = nums1[offset_1]
                    offset_1+=1
                else:
                    n1 = nums2[offset_2]
                    offset_2+=1
                if offset_1 == len(nums1):n2 = nums2[offset_2]
                elif offset_2 ==len(nums2): n2 =nums1[offset_1]
                else:n2 = min(nums1[offset_1],nums2[offset_2])
                #print(n1,n2)
                return (n1+n2)/2