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

題目描述

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

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

示例 1：

輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數組 = [1,2,3] ，中位數 2

示例 2：

輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數組 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

解題思路

這道題要求時間復雜度為 O(log(m+n))，這是一個經典的二分查找問題。

算法分析

這道題的核心思想是分割數組，主要解法包括：

1. 二分查找分割法：使用二分查找找到正確的分割點
2. 合并排序法：合并兩個數組后找中位數（不滿足時間復雜度要求）
3. 雙指針法：模擬合并過程（不滿足時間復雜度要求）

問題本質分析

graph TDA[尋找兩個正序數組中位數] --> B[分割策略]B --> C[二分查找分割點]B --> D[確保分割正確性]B --> E[計算中位數]C --> F[在較短數組中二分]D --> G[左半部分 ≤ 右半部分]E --> H[奇數取最大值]E --> I[偶數取平均值]F --> J[時間復雜度O_log_min_m_n]G --> K[邊界條件處理]H --> L[返回結果]I --> L

二分查找分割算法詳解

flowchart TDA[輸入兩個正序數組] --> B[確保nums1較短]B --> C[初始化二分查找范圍]C --> D[計算分割點i和j]D --> E[檢查分割是否有效]E --> F{分割有效?}F -->|是| G[計算中位數]F -->|否| H{調整方向}H -->|i太大| I[減小右邊界]H -->|i太小| J[增大左邊界]I --> DJ --> DG --> K[返回結果]D --> L[i = left+right/2]D --> M[j = m+n+1/2 - i]E --> N[檢查四個邊界值]N --> O[nums1[i-1] ≤ nums2[j]]N --> P[nums2[j-1] ≤ nums1[i]]

分割策略可視化

分割點計算過程

邊界情況處理

算法流程圖

flowchart TDA[開始] --> B[確保nums1較短]B --> C[初始化left=0, right=m]C --> D[left ≤ right?]D -->|否| E[返回0.0]D -->|是| F[計算i和j]F --> G[獲取四個邊界值]G --> H[檢查分割有效性]H --> I{分割有效?}I -->|是| J{總長度奇偶?}I -->|否| K{調整方向?}J -->|奇數| L[返回左半部分最大值]J -->|偶數| M[返回左右邊界平均值]K -->|i太大| N[right = i-1]K -->|i太小| O[left = i+1]N --> DO --> DL --> P[結束]M --> P

各種解法對比

時間復雜度分析

graph TDA[時間復雜度分析] --> B[二分查找]B --> C[查找范圍: min(m,n)]C --> D[每次查找: O_1]D --> E[總時間: O_log_min_m_n]E --> F[滿足題目要求O_log_m+n]F --> G[最優解法]

空間復雜度分析

關鍵優化點

實際應用場景

測試用例設計

代碼實現要點

1. 數組交換優化：

   • 確保nums1是較短的數組
   • 減少二分查找的范圍

2. 分割點計算：

   • i = (left + right) / 2
   • j = (m + n + 1) / 2 - i
   • 確保左右兩部分元素數量平衡

3. 邊界條件處理：

   • 使用math.MinInt32和math.MaxInt32
   • 處理數組邊界情況

4. 分割有效性檢查：

   • nums1[i-1] ≤ nums2[j]
   • nums2[j-1] ≤ nums1[i]

5. 中位數計算：

   • 奇數情況：max(nums1[i-1], nums2[j-1])
   • 偶數情況：(max + min) / 2

這個問題的關鍵在于理解分割策略和掌握二分查找技巧，通過巧妙的分割將兩個數組的問題轉化為單個數組的二分查找問題，實現高效的中位數計算。

完整題解代碼

package mainimport ("fmt""math"
)// findMedianSortedArrays 尋找兩個正序數組的中位數
// 時間復雜度: O(log(min(m,n)))
// 空間復雜度: O(1)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {// 確保nums1是較短的數組，這樣可以減少二分查找的范圍if len(nums1) > len(nums2) {nums1, nums2 = nums2, nums1}m, n := len(nums1), len(nums2)left, right := 0, m// 二分查找for left <= right {// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]i := (left + right) / 2j := (m+n+1)/2 - i// nums1[i-1], nums1[i], nums2[j-1], nums2[j] 分別表示// nums1 和 nums2 中前一部分的最大值和后一部分的最小值// 當 i = 0 時，nums1[i-1] 不存在，我們將其設為負無窮// 當 i = m 時，nums1[i] 不存在，我們將其設為正無窮nums1LeftMax := math.MinInt32if i > 0 {nums1LeftMax = nums1[i-1]}nums1RightMin := math.MaxInt32if i < m {nums1RightMin = nums1[i]}// 當 j = 0 時，nums2[j-1] 不存在，我們將其設為負無窮// 當 j = n 時，nums2[j] 不存在，我們將其設為正無窮nums2LeftMax := math.MinInt32if j > 0 {nums2LeftMax = nums2[j-1]}nums2RightMin := math.MaxInt32if j < n {nums2RightMin = nums2[j]}// 前一部分的最大值應該小于等于后一部分的最小值if nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin {// 找到了正確的分割點if (m+n)%2 == 1 {// 奇數個元素，中位數是前一部分的最大值return float64(max(nums1LeftMax, nums2LeftMax))} else {// 偶數個元素，中位數是前一部分的最大值和后一部分的最小值的平均值return float64(max(nums1LeftMax, nums2LeftMax)+min(nums1RightMin, nums2RightMin)) / 2.0}} else if nums1LeftMax > nums2RightMin {// nums1 的前一部分太大，需要減小right = i - 1} else {// nums1 的前一部分太小，需要增大left = i + 1}}// 正常情況下不會到達這里return 0.0
}// 輔助函數
func max(a, b int) int {if a > b {return a}return b
}func min(a, b int) int {if a < b {return a}return b
}func main() {// 測試用例1nums1 := []int{1, 3}nums2 := []int{2}result1 := findMedianSortedArrays(nums1, nums2)fmt.Printf("示例1: nums1 = %v, nums2 = %v\n", nums1, nums2)fmt.Printf("輸出: %.5f\n", result1)fmt.Println("期望: 2.00000")fmt.Println()// 測試用例2nums3 := []int{1, 2}nums4 := []int{3, 4}result2 := findMedianSortedArrays(nums3, nums4)fmt.Printf("示例2: nums1 = %v, nums2 = %v\n", nums3, nums4)fmt.Printf("輸出: %.5f\n", result2)fmt.Println("期望: 2.50000")fmt.Println()// 額外測試用例nums5 := []int{0, 0}nums6 := []int{0, 0}result3 := findMedianSortedArrays(nums5, nums6)fmt.Printf("額外測試: nums1 = %v, nums2 = %v\n", nums5, nums6)fmt.Printf("輸出: %.5f\n", result3)fmt.Println("期望: 0.00000")fmt.Println()nums7 := []int{}nums8 := []int{1}result4 := findMedianSortedArrays(nums7, nums8)fmt.Printf("額外測試: nums1 = %v, nums2 = %v\n", nums7, nums8)fmt.Printf("輸出: %.5f\n", result4)fmt.Println("期望: 1.00000")
}