ZeroJudge 解題筆記：c010. 10107 - What is the Median?

作者：王一哲
日期：2026年1月26日


ZeroJudge 題目連結：c010. 10107 - What is the Median?

解題想法

這題如果用串列，每次插入一個新的數字之後再排序、取中位數，這樣一定會超時。我試過以下兩種解法。第一種是用 C++ 的 priority_queue 及 Python 的 heapq 儲存資料，小於等於中位數的值儲存在最大優先佇列 small 之中，大於中位數的值儲存在最小優先佇列 large 之中，並且保持 small 的數量與 large 相等或是多一個。當讀取到一筆新的資料 x 時有三種可能性：

1. x 小於等於 small 最上面的資料：如果 small 的數量比 large 還多，將 small 最上面的資料移到 large。最後將 x 加入 small。
2. large 有資料而且 x 小於 large 最上面的資料： 如果 small 與 large 數量相等，將 x 加入 small，反之將 x 加入 large。
3. 其它狀況：如果 small 與 large 數量相等，將 large 最上面的資料移到 small。最後將 x 加入 large。

中位數有兩種可能性：

1. 如果 small 數量比 large 還多，中位數就是 small 最上面的資料。
2. 如果 small 與 large 數量相等，中位數是 small 與 large 最上面的資料平均值。

第二種解法是用 C++ algorithm 函式庫的 lower_bound 找出插入新資料並維持排序的位置，再用 vector.insert 插入新資料。在 Python 則可以用 bisect.insort 直接將新資料插入到 list 之中。由於這兩種工具是利用二分搜尋法找位置，速度相當快，寫起來也會比第一種法方簡單。

Python 程式碼

方法1，使用時間約為 21 ms，記憶體約為 4.2 MB，通過測試。

import sys, heapq

mid = int(sys.stdin.readline())
result = [f"{mid:d}\n"]
large, small = [], [-mid]
for line in sys.stdin:
    x = int(line)
    if x <= -small[0]:
        if len(small) > len(large):
            heapq.heappush(large, -heapq.heappop(small)) 
        heapq.heappush(small, -x)
    elif large and x < large[0]:
        if len(small) == len(large):
            heapq.heappush(small, -x) 
        else:
            heapq.heappush(large, x)
    else:
        if len(small) == len(large):
            heapq.heappush(small, -heapq.heappop(large))
        heapq.heappush(large, x)
    if len(small) > len(large):
        mid = -small[0]
    else:
        mid = (large[0] - small[0]) // 2
    result.append(f"{mid:d}\n")
sys.stdout.write("".join(result))

方法2，使用時間約為 26 ms，記憶體約為 4.8 MB，通過測試。

import sys
from bisect import insort

result = []
arr = []
lines = sys.stdin.readlines()
for line in lines:
    x = int(line)
    insort(arr, x)
    n = len(arr)
    if n%2 == 1:
        result.append(f"{arr[n//2]:d}\n")
    else:
        result.append(f"{(arr[n//2 - 1] + arr[n//2]) // 2:d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

方法1，使用時間約為 5 ms，記憶體約為 348 kB，通過測試。

#include <cstdio>
#include <queue>
#include <functional>
using namespace std;

int main() {
    int mid; scanf("%d", &mid);
    printf("%d\n", mid);
    priority_queue<int, vector<int>, greater<int>> large;
    priority_queue<int> small; small.push(mid);
    int x;
    while(scanf("%d", &x) != EOF) {
        if (x <= small.top()) {
            if (small.size() > large.size()) {
                large.push(small.top());
                small.pop();
            }
            small.push(x);
        } else if (!large.empty() && x < large.top()) {
            if (small.size() == large.size()) small.push(x); 
            else large.push(x);
        } else {
            if (small.size() == large.size()) {
                small.push(large.top());
                large.pop();
            }
            large.push(x);
        }
        if (small.size() > large.size()) mid = small.top();
        else mid = (large.top() + small.top()) / 2;
        printf("%d\n", mid);
    }
    return 0;
}

方法2，使用時間約為 6 ms，記憶體約為 364 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr;
    int x;
    while(scanf("%d", &x) != EOF) {
        auto it = lower_bound(arr.begin(), arr.end(), x);
        arr.insert(it, x);
        int n = (int)arr.size();
        if (n%2 == 1) {
            printf("%d\n", arr[n/2]);
        } else {
            printf("%d\n", (arr[n/2 - 1] + arr[n/2]) / 2);
        }
    }
    return 0;
}