方法一:

def median_1(A, B):# 思路一: 先組合成一個有序數列,再取中位數# 時間復雜度O(m+n)len_A = len(A)len_B = len(B)C = []if len_A == len_B == 0:raise ValueErrori = j = 0for k in range(0, len_A + len_B):if j == len_B or (i < len_A and A[i] <= B[j]):C.append(A[i])i += 1else:C.append(B[j])j += 1half = (len_A + len_B) // 2if (len_A + len_B) % 2 == 0:return (C[half - 1] + C[half]) / 2else:return C[half]

方法二:

def median_2(A, B):# 思路二: 沒有必要完全產生出第三個列表,我們在一開始就可以知道需要取的索引,且可以用變量記錄而不新建列表# 時間復雜度: O((m+n)/2) => O(m+n)len_A = len(A)len_B = len(B)if len_A == len_B == 0:raise ValueErrorhalf = (len_A + len_B) // 2 + 1pre = cur = i = j = 0for k in range(0, half):if j == len_B or (i < len_A and A[i] <= B[j]):pre = curcur = A[i]i += 1else:pre = curcur = B[j]j += 1if (len_A + len_B) % 2 == 0:return (pre + cur) / 2else:return cur

方法三:

def median_3(A, B, k=None):# 思路三: 求中位數的問題可以看作是求第(m+n)/2小的數的問題.如果是偶數個,則是第(m+n)/2小和第(m+n)/2+1小的均值.# 時間復雜度: O(log(m+n))# 更多Python視頻、源碼、資料加群725638078免費獲取m, n = len(A), len(B)if m > n:n, m, A, B = m, n, B, Aif n == 0:raise ValueErrorif k == None:k1 = (m + n + 1) // 2k2 = (m + n + 2) // 2return (median_3(A, B, k1) + median_3(A, B, k2)) / 2if m == 0:return B[k - 1]if k == 1:return A[0] if A[0] <= B[0] else B[0]half = k // 2index_A = min(m - 1, half - 1)index_B = min(n - 1, half - 1)if A[index_A] <= B[index_B]:return median_3(A[index_A + 1:], B, k - index_A - 1)else:return median_3(A, B[index_B + 1:], k - index_B - 1)

方法四:

def median_4(A, B):# 思路四:二分法, i = 0 ~ m, j = (m + n + 1) / 2 - i, 需保證j>=0, 即n>=m# 時間復雜度: O(log(min(m,n)))# 更多Python視頻、源碼、資料加群725638078免費獲取m, n = len(A), len(B)if m > n:m, n, A, B = n, m, B, Aif n == 0:raise ValueErrori_min = 0i_max = mhalf = (m + n + 1) // 2while i_min <= i_max:i = (i_min + i_max) // 2j = half - iif i > 0 and A[i - 1] > B[j]:# i太大了i_max = i - 1elif i < m and A[i] < B[j - 1]:# i太小了i_min = i + 1else:if i == 0:max_of_left = B[half - 1]elif j == 0:max_of_left = A[half - 1]else:max_of_left = max(A[i - 1], B[j - 1])if (m + n) % 2 == 1:return max_of_leftif i == m:min_of_right = B[j]elif j == n:min_of_right = A[i]else:min_of_right = min(A[i], B[j])return (max_of_left + min_of_right) / 2

結尾給大家推薦一個非常好的學習教程，希望對你學習Python有幫助！

Python基礎入門教程推薦：更多Python視頻教程-關注B站：Python學習者
https://www.bilibili.com/video/BV1LL4y1h7ny?share_source=copy_web

Python爬蟲案例教程推薦：更多Python視頻教程-關注B站：Python學習者
https://www.bilibili.com/video/BV1QZ4y1N7YA?share_source=copy_web

總結

以上是生活随笔為你收集整理的用四种方法Python求出两个有序数组中的中位数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。