题目描述

中位数定义：一组数据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两个数据的平均数）。

给出一组无序整数，求出中位数，如果求最中间两个数的平均数，向下取整即可（不需要使用浮点数）。

思路

判断奇偶，如果为奇输出中间数即可。
如果为偶输出中间两束的平局数即可

算法1

(模拟) $O(nm)$

C++ 代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e4 + 5 ;

int n ;

int main ( ) {

    while ( cin >> n ) {

        if ( !n ) return 0 ;

        int s[N] ;
        for ( int i = 1 ; i <= n ; i ++ ) cin >> s[i] ;

        sort ( s + 1 , s + n + 1 ) ;

        int mid ;
        if ( n % 2 ) mid = n / 2 + 1 ;
        else {

            cout << ( s[n / 2] + s[n / 2 + 1] ) / 2 << endl ; 
            continue ;

        }

        cout << s[mid] << endl ;

    }

    return 0 ;

}