python 找到两个排序数组的中位数_0004寻找两个有序数组的中位数.py

def findMedianSortedArrays(nums1, nums2):

m = len(nums1)

n = len(nums2)

if m > n:

nums1, nums2, m, n = nums2, nums1, n, m #保证m

if n == 0: #意味着两个数组同时为空

raise ValueError

left = 0

right = m

k = (m + n + 1)//2

print(m,n,left,right,k)

print('开始循环查找')

while left <= right:

print('l,r=',left,right)

i = (left + right)//2

j = k - i

print('i,j=',i,j)

if i < m and nums1[i] < nums2[j - 1]:

left = i + 1

print(left)

elif i > 0 and nums2[j] < nums1[i - 1]:

right = i - 1

else:

if i == 0:

maxofleft = nums2[j-1]

elif j == 0:

maxofleft = nums1[i-1]

else:

maxofleft = max(nums1[i-1], nums2[j-1])

if (m + n)%2 == 1:

return maxofleft

if i == m:

minofright = nums2[j]

elif j == n:

minofright = nums1[i]

else:

minofright = min(nums1[i], nums2[j])

return (maxofleft + minofright)/2.0

n1 = [1,3]

n2 = [2]

print(findMedianSortedArrays(n1, n2))

一键复制

编辑

Web IDE

原始数据

按行查看

历史