題目描述
給定兩個已排序的陣列 nums1 和 nums2，請找到並返回這兩個陣列的中位數。要求時間複雜度為 O(log(min(m, n)))，其中 m 和 n 分別是兩個陣列的長度。
- 輸入：
nums1 = [1, 3],nums2 = [2]
輸出：2.0 - 輸入：
nums1 = [1, 2],nums2 = [3, 4]
輸出：2.5
解題思路
中位數問題在兩個已排序陣列中可以透過二分搜尋來解決。為了達成 O(log(min(m, n))) 的時間複雜度要求，我們可以在較短的陣列中進行二分搜尋，從而縮小運算範圍。
思路概述：
- 分割陣列：將兩個陣列視為一整體，分割成兩部分，使得左邊部分的數量等於右邊部分。
- 選擇左側最大值和右側最小值：中位數即是左側最大值和右側最小值的平均數或其中一個。
- 二分搜尋優化：在較短的陣列中進行分割調整，直至找到合適的分割點，使得左側的數字都小於右側。
解法一：二分搜尋
在這裡，我們以較短的陣列進行二分搜尋。透過在 nums1 中調整分割點，可以計算出 nums2 中相應的分割位置，並驗證是否滿足條件。最終的分割結果即為中位數。
步驟詳解：
- 確保
nums1是較短的陣列（如果不是，交換nums1和nums2）。 - 設置
low和high為nums1的左右邊界。 - 在
nums1中進行二分搜尋，計算分割點partition1和partition2。 - 確認條件：
- 若
nums1[partition1 - 1] <= nums2[partition2]且nums2[partition2 - 1] <= nums1[partition1]，則找到合適的分割點。
- 若
- 計算中位數：
- 若兩陣列總長度為奇數，則中位數為左側最大值。
- 若總長度為偶數，中位數為左側最大值與右側最小值的平均。
程式碼實現：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 確保 nums1 是較短的陣列
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
low, high = 0, m
while low <= high:
partition1 = (low + high) // 2
partition2 = (m + n + 1) // 2 - partition1
# 邊界情况
max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
min_right1 = float('inf') if partition1 == m else nums1[partition1]
max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
min_right2 = float('inf') if partition2 == n else nums2[partition2]
if max_left1 <= min_right2 and max_left2 <= min_right1:
if (m + n) % 2 == 0:
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
else:
return max(max_left1, max_left2)
elif max_left1 > min_right2:
high = partition1 - 1
else:
low = partition1 + 1
- 時間複雜度：
O(log(min(m, n)))，因為我們在較短的陣列中進行二分搜尋。 - 空間複雜度：
O(1)，僅使用常數空間來存儲指標和變量。
解法二：合併排序法
另一種解法是合併兩個排序陣列，但這種解法的時間複雜度為 O(m + n)，不符合題目要求的 O(log(min(m, n)))。儘管如此，若不考慮時間限制，這種方法對理解中位數概念有幫助。
步驟詳解：
- 將兩個陣列合併。
- 將合併過後的陣列排序。
- 如果合併過後長度為奇數，返回中間值；若為偶數，返回兩個中間值的平均數。
程式碼實現：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
list_combined = []
# 合併兩個陣列
list_combined = nums1 + nums2
# 排序陣列
list_combined.sort()
# 計算中位數
if len(list_combined) % 2 == 0:
return (list_combined[int(len(list_combined) * 0.5) - 1] + list_combined[int(len(list_combined) * 0.5)]) / 2.0
else:
return list_combined[floor(len(list_combined) * 0.5)]
- 時間複雜度：
O(m + n)，因為需要遍歷兩個陣列並將所有元素合併到一個新陣列中。 - 空間複雜度：
O(m + n)，因為使用了額外的空間來儲存合併的陣列。
小結
這道題主要測試二分搜尋在數組合併與排序中的應用。解法一通過較短陣列的二分搜尋，巧妙地達到 O(log(min(m, n))) 的時間複雜度，是處理中位數問題的最優解法。
