python 找到兩個排序數組的中位數_4. 尋找兩個有序數組的中位數（Python）

題目

(難)給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。請你找出這兩個有序數組的中位數，并且要求算法的時間複雜度為 O(log(m + n))。你可以假設 nums1 和 nums2 不會同時為空。

示例

示例 1:

nums1 = [1, 3]

nums2 = [2]

則中位數是 2.0

示例 2:

nums1 = [1, 2]

nums2 = [3, 4]

則中位數是 (2 + 3)/2 = 2.5

解答

解法1：

最簡單的解法是暴力求解

實際上是希望我們實作下面的算法：

class Solution:

def findMedianSortedArrays(self, nums1, nums2):

both = sorted(nums1 + nums2) # 合并兩個連結清單

l = len(both)

# 計算中位數

if l % 2 == 0:

return sum(both[l//2-1:l//2+1]) / 2

else:

return both[l//2]

很意外，用時居然超過了絕大多數使用者。。

執行用時 : 80 ms, 在Median of Two Sorted Arrays的Python3送出中擊敗了96.83% 的使用者

記憶體消耗 : 13.3 MB, 在Median of Two Sorted Arrays的Python3送出中擊敗了65.59% 的使用者

如果需要我們實作上面“both = sorted(nums1 + nums2) ”這句話呢？好在兩個清單都是有序的，我們隻需要寫一個函數，用于合并兩個有序清單，并使整體有序。時間可達128ms。

class Solution:

def findMedianSortedArrays(self, nums1, nums2):

def merge(nums1, nums2): # 合并兩個有序連結清單，使結果有序

result = [] # 結果數組

while nums1 or nums2:

if not nums1:

result += nums2

break

if not nums2:

result += nums1

break

if nums1[0] > nums2[0]:

result.append(nums2.pop(0)) # 彈出nums2中最小數到result最後

else:

result.append(nums1.pop(0)) # 彈出nums1中最小數到result最後

return result

both = merge(nums1, nums2)

l = len(both)

if l % 2 == 0:

return sum(both[l//2-1:l//2+1]) / 2

else:

return both[l//2]

上面基本的解答都可以通過，不過，這道題目的本意貌似要用一些其他刁鑽技巧，這裡直接摘網上的答案吧。

class Solution:

def findMedianSortedArrays(self, nums1, nums2):

"""

:type nums1: List[int]

:type nums2: List[int]

:rtype: float

"""

m, n = len(nums1), len(nums2)

if m > n:

nums1, nums2, m, n = nums2, nums1, n, m

if n == 0:

raise ValueError

imin, imax, half_len = 0, m, (m + n + 1) // 2

while imin <= imax:

i = (imin + imax) // 2

j = half_len - i

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

# i is too small, must increase it

imin = i + 1

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

# i is too big, must decrease it

imax = i - 1

else:

# i is perfect

if i == 0: max_of_left = nums2[j-1]

elif j == 0: max_of_left = nums1[i-1]

else: max_of_left = max(nums1[i-1], nums2[j-1])

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

return max_of_left

if i == m: min_of_right = nums2[j]

elif j == n: min_of_right = nums1[i]

else: min_of_right = min(nums1[i], nums2[j])

return (max_of_left + min_of_right) / 2.0

如有疑問，歡迎評論區留言。