[LeetCode解題攻略] 4. Median of Two Sorted Arrays

題目描述

給定兩個已排序的陣列 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))) 的時間複雜度要求，我們可以在較短的陣列中進行二分搜尋，從而縮小運算範圍。

思路概述：

1. 分割陣列：將兩個陣列視為一整體，分割成兩部分，使得左邊部分的數量等於右邊部分。
2. 選擇左側最大值和右側最小值：中位數即是左側最大值和右側最小值的平均數或其中一個。
3. 二分搜尋優化：在較短的陣列中進行分割調整，直至找到合適的分割點，使得左側的數字都小於右側。

解法一：二分搜尋

在這裡，我們以較短的陣列進行二分搜尋。透過在 nums1 中調整分割點，可以計算出 nums2 中相應的分割位置，並驗證是否滿足條件。最終的分割結果即為中位數。

步驟詳解：

1. 確保 nums1 是較短的陣列（如果不是，交換 nums1 和 nums2）。
2. 設置 low 和 high 為 nums1 的左右邊界。
3. 在 nums1 中進行二分搜尋，計算分割點 partition1 和 partition2。
4. 確認條件：
5. • 若 nums1[partition1 - 1] <= nums2[partition2] 且 nums2[partition2 - 1] <= nums1[partition1]，則找到合適的分割點。
5. 計算中位數：
6. • 若兩陣列總長度為奇數，則中位數為左側最大值。
   • 若總長度為偶數，中位數為左側最大值與右側最小值的平均。

程式碼實現：

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)))。儘管如此，若不考慮時間限制，這種方法對理解中位數概念有幫助。

步驟詳解：

1. 將兩個陣列合併。
2. 將合併過後的陣列排序。
3. 如果合併過後長度為奇數，返回中間值；若為偶數，返回兩個中間值的平均數。

程式碼實現：

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))) 的時間複雜度，是處理中位數問題的最優解法。