您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

LeetCode 004 兩個有序數組中位數：O(log(m+n)) 二分遞歸完美解法

編輯：Java 綜合教學

Hard 級經典：雙有序數組中位數的對數時間解法深度剖析

LeetCode 4 題要求在 O(log(m+n)) 時間內找出兩個已排序數組的中位數。暴力合併 O(m+n) 易想但不達標；核心思路是二分法每次排除 k/2 個不可能的元素，將問題規模指數級縮小。本文提供完整遞歸實現、邊界條件處理、測試驗證及複雜度證明。

一、題目重述

給定兩個大小為 m、n 的有序數組 nums1、nums2，找出它們的中位數。要求時間復雜度 O(log(m+n))。
示例 1：nums1=[1,3], nums2=[2] → 中位數 2.0
示例 2：nums1=[1,2], nums2=[3,4] → 中位數 (2+3)/2 = 2.5

二、核心算法：遞歸排除法

關鍵洞察

中位數即第 (m+n+1)/2 小（奇數）與第 (m+n+2)/2 小（偶數）的平均。
比較兩數組第 k/2 個元素，較小者及其之前的元素必不可能是第 k 小，可直接排除。
遞歸求第 k 小，k 每次減半，時間 O(log k) = O(log(m+n))。

遞歸函數簽名

double findKth(int[] A, int aStart, int[] B, int bStart, int k)

三、完整 Java 實現（生產級健壯版）

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int left = (m + n + 1) >> 1;
        int right = (m + n + 2) >> 1;
        // 奇數時 left==right，偶數時取平均
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    private double findKth(int[] A, int aStart, int[] B, int bStart, int k) {
        // 確保 A 是較短數組，簡化邊界判斷
        if (A.length - aStart > B.length - bStart) {
            return findKth(B, bStart, A, aStart, k);
        }
        // A 已耗盡，直接在 B 中取第 k 個
        if (aStart >= A.length) return B[bStart + k - 1];
        // k=1 直接返回兩數組當前首元素較小者
        if (k == 1) return Math.min(A[aStart], B[bStart]);

        // 取雙方第 k/2 個元素（不越界）
        int aMid = Math.min(aStart + k/2 - 1, A.length - 1);
        int bMid = Math.min(bStart + k/2 - 1, B.length - 1);

        if (A[aMid] <= B[bMid]) {
            // 排除 A[aStart..aMid]，共排除 aMid - aStart + 1 個
            return findKth(A, aMid + 1, B, bStart, k - (aMid - aStart + 1));
        } else {
            // 排除 B[bStart..bMid]
            return findKth(A, aStart, B, bMid + 1, k - (bMid - bStart + 1));
        }
    }
}

四、邊界條件詳解

一個數組為空：直接在另一數組取中位數，代碼通用處理無需特判。
k=1：終止條件，返回當前首元素最小值。
數組長度不足 k/2：Math.min 保護索引，實際排除數量按實際長度計算。
重複元素：<= 保證穩定排除，不影響正確性。
整數溢出：索引運算用 int 足夠（數組長度 < Integer.MAX_VALUE），中位數計算用 2.0 強制 double 除法。

五、複雜度證明

時間：每次遞歸 k 減少約一半，遞歸深度 ≤ log₂(m+n)，每層 O(1) → O(log(m+n))。
空間：遞歸棧深度 O(log(m+n))，可改寫為迭代降為 O(1)。

六、測試用例驗證

@Test
public void test() {
    MedianOfTwoSortedArrays solver = new MedianOfTwoSortedArrays();
    assertEquals(2.0, solver.findMedianSortedArrays(new int[]{1,3}, new int[]{2}), 1e-9);
    assertEquals(2.5, solver.findMedianSortedArrays(new int[]{1,2}, new int[]{3,4}), 1e-9);
    assertEquals(1.0, solver.findMedianSortedArrays(new int[]{}, new int[]{1}), 1e-9);
    assertEquals(2.0, solver.findMedianSortedArrays(new int[]{1,2}, new int[]{3,4,5}), 1e-9);
    assertEquals(3.0, solver.findMedianSortedArrays(new int[]{1,2,3,4,5}, new int[]{6,7,8,9,10}), 1e-9);
    // 大數組性能測試
    int[] A = new int[100000]; for (int i=0;i

七、常見變體擴展

三個/多個有序數組中位數：兩兩合併或推廣為 K 路歸併堆 + 二分答案。
動態流中位數：雙堆（大根堆+小根堆）維護，O(log n) 插入、O(1) 取中位數。
矩陣中位數：按值二分 + 每行二分計數，O(m log n log Max)。


八、總結
LeetCode 4 是「二分答案 + 雙指針排除」思想的教科書級應用。關鍵在於將「找中位數」轉化為「找第 k 小」，並利用有序性大膽排除不可能區間。掌握此題模板，同類「K-th in sorted matrix/arrays」題型皆可迎刃而解。