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

原始資料

按行檢視

曆史