HDU 1157 Who's in the Middle：中位數查找水題

HDU 1157 Who's in the Middle：中位數查找水題

給定奇數 N (≤ 10000) 頭奶牛產奶量，求中位數（排序後第 (N+1)/2 小）。

解法

• 讀入數組，sort 排序。
• 輸出 arr[(N-1)/2]（0-based 索引）。

代碼

#include 
#define maxn 10002
int arr[maxn];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i=0; i>1]);
    }
    return 0;
}

複雜度

• 時間：O(N log N)。
• 空間：O(N)。

標準庫 sort 即可通過，無需手寫快選算法。注意 N 為奇數保證中位數唯一。