4. 尋找兩個正序數組的中位數

博主只會第一個暴力解法，然后將官網上的源碼上添加些注釋，嘗試理解，分下今日刷題記錄

題目描述

給定兩個大小分別為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并返回這兩個正序數組的 中位數 。

算法的時間復雜度應該為 O(log (m+n))

解法一：暴力合并法（不符合題目要求的時間復雜度）

這種方法最為直觀，但時間復雜度為 O((m+n)log(m+n))，不符合題目要求。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:nums = sorted(nums1 + nums2)  # 合并并排序兩個數組n = len(nums)result = 0for i in range(n):result += nums[i]return result / n  # 這里實際上計算的是平均值而非中位數，正確的中位數計算應為：# 如果n為奇數，返回nums[n//2]# 如果n為偶數，返回(nums[n//2-1] + nums[n//2])/2

注意：上述代碼中計算的是平均值而非中位數。正確的中位數計算應該是：

if n % 2 == 1:return nums[n//2]
else:return (nums[n//2-1] + nums[n//2]) / 2

解法二：二分查找法（符合題目要求的時間復雜度）

這種方法的核心思想是將"尋找中位數"轉化為"尋找第k小的元素"的問題。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:def getKthElement(k):"""- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較- 這里的 "/" 表示整除- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個- 取 pivot = min(pivot1, pivot2)，兩個數組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個- 這樣 pivot 本身最大也只能是第 k-1 小的元素- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums1 數組- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums2 數組- 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要小），因此需要修改 k 的值，減去刪除的數的個數"""index1, index2 = 0, 0  # 初始化兩個數組的起始索引while True:# 特殊情況處理if index1 == m:  # m是數組num1的長度，如果nums1已經全部被排除return nums2[index2 + k - 1]  # 直接返回nums2中的第k個元素if index2 == n:  #n是數組num2的長度 如果nums2已經全部被排除return nums1[index1 + k - 1]  # 直接返回nums1中的第k個元素if k == 1:  # 如果要找第1小的元素return min(nums1[index1], nums2[index2])  # 返回兩個數組當前位置的最小值# 正常情況處理newIndex1 = min(index1 + k // 2 - 1, m - 1)  # 計算nums1中的比較位置，防止越界newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 計算nums2中的比較位置，防止越界pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]  # 取出比較值# 比較兩個數組的元素，排除較小元素所在的部分if pivot1 <= pivot2:  # 如果nums1的元素較小k -= newIndex1 - index1 + 1  # 更新k值，減去排除的元素個數index1 = newIndex1 + 1  # 更新nums1的起始位置else:  # 如果nums2的元素較小k -= newIndex2 - index2 + 1  # 更新k值，減去排除的元素個數index2 = newIndex2 + 1  # 更新nums2的起始位置m, n = len(nums1), len(nums2)  # 獲取兩個數組的長度totalLength = m + n  # 計算總長度# 根據總長度的奇偶性，計算中位數if totalLength % 2 == 1:  # 如果總長度為奇數return getKthElement((totalLength + 1) // 2)  # 返回中間的元素else:  # 如果總長度為偶數return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2  # 返回中間兩個元素的平均值

詳細解釋

二分查找法的核心思想

1. 問題轉化：中位數可以轉化為找第k小的元素

   • 如果總長度為奇數，中位數是第(m+n+1)/2小的元素
   • 如果總長度為偶數，中位數是第(m+n)/2小和第(m+n)/2+1小的元素的平均值

2. 二分排除法：每次比較兩個數組中第k/2個元素，排除較小值所在數組的前k/2個元素

算法流程圖解

假設有兩個數組：

• nums1 = [1, 3, 5, 7, 9]
• nums2 = [2, 4, 6, 8, 10]

要找這兩個數組合并后的中位數：

1. 總長度為10，是偶數，需要找第5小和第6小的元素的平均值
2. 尋找第5小的元素：
   • 比較nums1[5/2-1]=nums1[1]=3和nums2[5/2-1]=nums2[1]=4
   • 3<4，排除nums1的[1,3]，k=3，nums1現在從索引2開始
   • 比較nums1[3/2-1+2]=nums1[3]=7和nums2[3/2-1]=nums2[0]=2
   • 7>2，排除nums2的[2]，k=2，nums2現在從索引1開始
   • 比較nums1[2/2-1+2]=nums1[2]=5和nums2[2/2-1+1]=nums2[1]=4
   • 5>4，排除nums2的[4]，k=1，nums2現在從索引2開始
   • k=1，返回min(nums1[2], nums2[2])=min(5,6)=5
3. 尋找第6小的元素（類似過程）：結果為6
4. 中位數=(5+6)/2=5.5

時間復雜度分析

• 每次操作會排除k/2個元素
• 總共有m+n個元素，最多需要log(m+n)次操作
• 因此時間復雜度為O(log(m+n))，符合題目要求

空間復雜度分析

• 只使用了常數級別的額外空間
• 空間復雜度為O(1)

總結

1. 暴力合并法：簡單直觀但不符合題目要求
2. 二分查找法：通過每次排除一部分元素，達到O(log(m+n))的時間復雜度
3. 關鍵在于將"尋找中位數"轉化為"尋找第k小元素"的問題
4. 通過比較兩個數組中第k/2個元素，每次可以排除至少k/2個元素