# Untitled

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```