Untitled
plain_text
8 days 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