一、文章標題

LeetCode 004. 尋找兩個正序數組的中位數 - 二分切分與分治詳解

二、文章內容

1. 題目概述

• 題目描述：給定兩個已按非降序排列的整數數組 nums1、nums2，設它們長度分別為 m 和 n，要求返回這兩個數組合并后有序序列的中位數。整體期望時間復雜度為 O(log(m+n))。當總長度為偶數時，中位數為中間兩個數的平均值（返回 double）。數組可能為空，但不會同時為空（若實現中遇到同時為空需返回默認值）。
• 原題鏈接：https://leetcode.cn/problems/median-of-two-sorted-arrays/
• 難度等級：Hard
• 相關標簽：數組、二分查找、分治、雙指針

2. 文章目錄

目錄

1. 題目概述
2. 解題思路
3. 算法詳解
   • 3.1 解法一：雙指針線性掃描到中位數
   • 3.2 解法二：二分切分（最優）
4. 解法對比
5. 最優解推薦

3. 解題思路

• 問題分析：
  • 輸入：兩個已排序的整型數組 nums1、nums2。
  • 輸出：合并后序列的中位數（double）。
  • 中位數定義：
    • 若 m+n 為奇數，中位數為第 (m+n)/2（0 基）處的元素。
    • 若 m+n 為偶數，中位數為第 (m+n)/2 - 1 與 (m+n)/2 兩個元素均值。
• 核心難點：
  • 在不真正合并數組的前提下，以 O(log(m+n)) 時間找到中位數。
  • 復雜邊界處理：空數組、分割端點在數組兩側、奇偶長度處理、整型轉 double。
• 解題方向：
  1. 線性合并/掃描到中位數位置（O(m+n)，實現直觀，作為兜底）。
  2. 分治/找第 k 小（每輪丟棄 k/2 個元素，O(log(m+n))）。
  3. 二分切分（只對較短數組二分，構造左右兩半滿足有序關系，O(log(min(m,n)))，最優）。

4. 算法詳解

解法一：雙指針線性掃描到中位數

算法原理

• 核心思想：像歸并排序的合并過程一樣，用兩根指針從頭掃描兩個有序數組，不必真的合并，只需走到中位數所在下標就停止。
• 適用場景：當不強求 O(log(m+n))、或用作對拍與兜底實現時非常好用。

具體實現

• 步驟1：準備兩個指針 i、j 指向 nums1、nums2 開始位置，準備計數 idx 表示當前合并到的下標。
• 步驟2：每次取兩個指針中較小的元素作為“當前值”，并向前推進對應指針，直到走到右側中位數下標 mid2。
• 步驟3：根據總長度奇偶，返回 curr 或 (prev+curr)/2.0。

復雜度分析

• 時間復雜度：O(m+n)，最壞需要掃描完所有元素。
• 空間復雜度：O(1)，只用到常數額外變量。

Java代碼實現

class Solution {/*** 線性掃描到中位數位置的解法（O(m+n)）。* 注意：為講解清晰，方法名與最優解區分；在 LeetCode 提交時可將最優解方法名改為題目要求的方法名。*/public double findMedianSortedArraysLinear(int[] nums1, int[] nums2) {// 將 null 視作空數組，避免空指針if (nums1 == null) nums1 = new int[0];if (nums2 == null) nums2 = new int[0];int m = nums1.length, n = nums2.length;int total = m + n;// 題目一般保證不會同時為空；為健壯性，這里返回默認值 0.0if (total == 0) {return 0.0;}// 左、右中位數的目標下標（0 基）int mid1 = (total - 1) / 2; // 左中位數int mid2 = total / 2;       // 右中位數int i = 0, j = 0;  // 兩個數組的掃描指針int idx = -1;      // 已經“取出”的元素個數 - 1int prev = 0;      // 上一個取出的值（用于偶數總長度）int curr = 0;      // 當前取出的值// 掃描直到到達右中位數位置while (idx < mid2) {prev = curr; // 記錄上一個值// 取較小值推進（當某一數組用盡時，取另一數組）if (i < m && (j >= n || nums1[i] <= nums2[j])) {curr = nums1[i++];} else if (j < n) {curr = nums2[j++];}idx++;}// 奇偶分別處理if ((total & 1) == 1) {return curr; // 奇數長度，中位數就是當前值} else {return (prev + curr) / 2.0; // 偶數長度，取均值}}
}

---

解法二：二分切分（最優）

算法原理

• 基本思想：只對較短的數組進行二分，在兩個數組上找到一個“切分點對” (i, j)，使得：
  • 左半部分長度等于右半部分長度（或只多 1），即 i + j = (m + n + 1) / 2；
  • 左半最大值 ≤ 右半最小值，即 max(A[i-1], B[j-1]) ≤ min(A[i], B[j])。
• 一旦上述條件成立：
  • 若總長度為奇數，中位數是左半最大值；
  • 若為偶數，中位數是左半最大值與右半最小值的平均。
• 適用場景：追求最優時間復雜度，面試高頻且邊界清晰的標準解。

具體實現

• 步驟1：確保對更短的數組二分，令 A 為短數組，B 為長數組。
• 步驟2：在 A 的 [0…m] 區間二分 i，令 j = (m+n+1)/2 - i。
• 步驟3：檢查是否滿足分割條件；若 A[i-1] > B[j]，說明 i 偏大，收縮右邊；若 B[j-1] > A[i]，說明 i 偏小，收縮左邊；否則命中答案。

復雜度分析

• 時間復雜度：O(log(min(m,n)))，只在短數組長度范圍內二分。
• 空間復雜度：O(1)，常數額外空間。

Java代碼實現

class Solution {/*** 最優解：二分切分，時間復雜度 O(log(min(m,n)))，空間 O(1)。* 若兩個數組都為空則返回 0.0 作為默認值，避免拋異常。*/public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 將 null 視作空數組，避免空指針if (nums1 == null) nums1 = new int[0];if (nums2 == null) nums2 = new int[0];// 始終讓 A 為較短數組，B 為較長數組int[] A = nums1.length <= nums2.length ? nums1 : nums2;int[] B = (A == nums1) ? nums2 : nums1;int m = A.length, n = B.length;// 邊界：兩個都為空，返回默認值if (m + n == 0) {return 0.0;}int left = 0, right = m; // 在 A 的切分位置范圍 [0..m] 上二分int half = (m + n + 1) / 2; // 左半部分應包含的元素個數while (left <= right) {int i = left + (right - left) / 2; // A 的切分點int j = half - i;                  // B 的切分點，使得左半長度滿足要求// 處理邊界元素，越界時使用極小/極大的“哨兵”思想（用比較邏輯避免實際越界）int Aleft  = (i == 0) ? Integer.MIN_VALUE : A[i - 1];int Aright = (i == m) ? Integer.MAX_VALUE : A[i];int Bleft  = (j == 0) ? Integer.MIN_VALUE : B[j - 1];int Bright = (j == n) ? Integer.MAX_VALUE : B[j];// 檢查是否滿足切分正確：左邊最大 <= 右邊最小if (Aleft <= Bright && Bleft <= Aright) {// 命中：根據奇偶直接計算中位數if (((m + n) & 1) == 1) {// 奇數：中位數是左邊最大值int leftMax = Math.max(Aleft, Bleft);return (double) leftMax;} else {// 偶數：中位數是 左邊最大 與 右邊最小 的均值int leftMax = Math.max(Aleft, Bleft);int rightMin = Math.min(Aright, Bright);return (leftMax + rightMin) / 2.0;}} else if (Aleft > Bright) {// A 的左邊太大，i 需要左移right = i - 1;} else {// Bleft > Aright，i 需要右移left = i + 1;}}// 理論上一定能在循環內返回；為健壯性返回默認值return 0.0;}
}

5. 解法對比與總結

解法	時間復雜度	空間復雜度	優點	缺點	適用場景
雙指針線性掃描到中位數	O(m+n)	O(1)	實現直觀、邊界簡單、易調試	不滿足題目要求的對數級時間	數據量不大、或作為兜底與對拍
二分切分（最優）	O(log(min(m,n)))	O(1)	滿足最優時間、無需額外空間、思路標準	邊界處理細節較多，上手需練習	面試高頻、追求最優性能

最優解推薦：二分切分。其時間復雜度 O(log(min(m,n)))，空間 O(1)，能嚴格滿足題目對數級要求，且是工業界與面試中的標準寫法，值得熟練掌握。

三、文章標簽

算法,二分查找,LeetCode,困難,數組,雙指針,分治

四、文章簡述

本題考察兩個有序數組的中位數，給出線性雙指針與二分切分兩種方案。重點講解邊界處理、奇偶長度與復雜度分析，附帶完整 Java 實現與注釋，含對比與選型建議，適合面試與算法進階讀者。