LeetCode Median of Two Sorted Arrays：O(log(m+n)) 找中位數

題目簡介

給定兩個已排序數組，求合併後的中位數。要求時間複雜度 O(log(m+n))。中位數定義：總長度奇數取中間，偶數取中間兩數平均。

解題思路

轉化為求第 k 小元素問題。遞歸函數 findKth(A, m, B, n, k)：

• 確保 m ≤ n，若 m=0 直接返回 B[k-1]。
• 若 k=1 返回 min(A[0], B[0])。
• 取 ia = min(k/2, m), ib = k - ia。
• 比較 A[ia-1] 和 B[ib-1]，排除較小者對應的前 ia 或 ib 個元素，遞歸求剩餘第 k-ia 或 k-ib 小。

中位數：總長 L = m+n，若 L 奇數求第 (L/2+1) 小，偶數求第 L/2 和 L/2+1 小的平均。

代碼實現

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int total = m + n;
        if (total & 1) return findKth(nums1, nums2, total/2 + 1);
        else return (findKth(nums1, nums2, total/2) + findKth(nums1, nums2, total/2 + 1)) / 2.0;
    }
private:
    int findKth(vector<int>& A, vector<int>& B, int k) {
        int m = A.size(), n = B.size();
        if (m > n) return findKth(B, A, k);
        if (m == 0) return B[k-1];
        if (k == 1) return min(A[0], B[0]);
        int ia = min(k/2, m), ib = k - ia;
        if (A[ia-1] < B[ib-1]) {
            A.erase(A.begin(), A.begin()+ia);
            return findKth(A, B, k-ia);
        } else if (A[ia-1] > B[ib-1]) {
            B.erase(B.begin(), B.begin()+ib);
            return findKth(A, B, k-ib);
        } else return A[ia-1];
    }
};

複雜度分析

每次遞歸排除 k/2 元素，深度 O(log k)，總時間 O(log(m+n))。空間 O(log(m+n)) 遞歸棧（可改迭代為 O(1)）。