LeetCode 解題筆記：4. Median of Two Sorted Arrays

作者：王一哲
日期：2026年7月17日


LeetCode 題目連結：4. Median of Two Sorted Arrays

解題想法

困難題。題目給兩個已經由小到大排序好的陣列 $nums1$ 及 $nums2$，要找出兩個陣列合併後的中位數，如果合併後陣列中整數數量 $n$ 為奇數，中位數是索引值為 $\left \lfloor n/2 \right \rfloor$ 的數字；如果數量為偶數，中位數則是取索引值為 $n/2 - 1$ 及 $n/2$ 兩個數的平均值。

由於我以前在 ZeroJudge 寫過類似的題目，比較直覺的想法是用一個最小優先佇列 $large$ 儲存目前大於中位數的數字，用一個最大優先佇列 $small$ 儲存目前小於中位數的數字，用一個 for 迴圈依序取出陣列中的數字 $x$，拿 $x$ 與 $large$ 及 $small$ 最上面的值比大小，決定 $x$ 要放入 $large$ 或是 $small$；再調整 $large$ 與 $small$ 的長度，讓兩者長度相同或是 $small$ 比 $large$ 多一項。這個寫法能夠過關，但是速度不夠快。

另一個寫法是依序取出 $nums1$ 及 $nums2$ 的數字 $x$，利用內建的二分搜尋法工具找到 $x$ 於合併後的陣列 $nums$ 之中插入數字並保持由小到大排序的索引值。這個寫法程式碼很簡單，速度也快很多。

Python 程式碼

Runtime: 18 ms, beats 5.26%. Memory: 19.68 MB, beats 14.45%.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        large, small = [], []
        nums = nums1[:] + nums2[:]
        for x in nums:
            if not small or x < -small[0]:
                heapq.heappush(small, -x)
            else:
                heapq.heappush(large, x)
            if len(small) > len(large) + 1:
                v = -heapq.heappop(small)
                heapq.heappush(large, v)
            if len(large) > len(small):
                v = heapq.heappop(large)
                heapq.heappush(small, -v)
        mid = -small[0]
        if len(small) == len(large):
            mid = (-small[0] + large[0]) * 0.5
        return mid

Runtime: 7 ms, beats 13.14%. Memory: 19.72 MB, beats 14.45%.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = []
        for x in nums1:
            bisect.insort(nums, x)
        for x in nums2:
            bisect.insort(nums, x)
        
        n = len(nums)
        if n % 2 == 1:
            return nums[n//2]
        else:
            return (nums[n//2 - 1] + nums[n//2]) * 0.5
        return mid

C++ 程式碼

Runtime: 4 ms, beats 19.05%. Memory: 96.10 MB, beats 9.65%.

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        priority_queue<int, vector<int>, greater<int>> large;
        priority_queue<int> small;
        for(int x : nums1) {
            if (small.empty() || x < small.top()) {
                small.push(x);
            } else {
                large.push(x);
            }
            if (small.size() > large.size() + 1) {
                int v = small.top();
                small.pop();
                large.push(v);
            }
            if (large.size() > small.size()) {
                int v = large.top();
                large.pop();
                small.push(v);
            }
        }

        for(int x : nums2) {
            if (small.empty() || x < small.top()) {
                small.push(x);
            } else {
                large.push(x);
            }
            if (small.size() > large.size() + 1) {
                int v = small.top();
                small.pop();
                large.push(v);
            }
            if (large.size() > small.size()) {
                int v = large.top();
                large.pop();
                small.push(v);
            }
        }
        
        double mid = small.top();
        if (small.size() == large.size()) {
            mid = (small.top() + large.top()) * 0.5;
        }
        return mid;
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 96.05 MB, beats 9.65%.

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums;
        for(int x : nums1) {
            auto it = lower_bound(nums.begin(), nums.end(), x);
            nums.insert(it, x);
        }

        for(int x : nums2) {
            auto it = lower_bound(nums.begin(), nums.end(), x);
            nums.insert(it, x);
        }
        
        int n = (int)nums.size();
        if (n%2 == 1) {
            return nums[n/2];
        } else {
            return (nums[n/2 - 1] + nums[n/2]) * 0.5;
        }
    }
};