求中位数的思路?我是不懂输入的数中有相等的数这种情况。。排除先排序再找中位数的思路。

杜若熏风 发布于 2017/07/29 13:03
阅读 106
收藏 0

给出一组无序整数,求出中位数,如果求最中间两个数的平均数,向下取整即可(不需要使用浮点数)
我纠结的地方在于输入的数里假如是这样的:5 1 2 2 8 0,就有相等的就没法处理了

提示

这是也一道经典的算法问题,在企业面试里出现概率很高,是“找到第K大的数”的变种。先排序再找中位数自然是很直接的做法,但排序本身很慢。我们只想找到第n/2大的数,对于其他数的顺序我们并不关心。那么怎么在不排序的前提下找到第n/2大的数呢

中位数定义:一组数据按从小到大的顺序依次排列,处在中间位置的一个数或最中间两个数据的平均值(如果这组数的个数为奇数,则中位数为位于中间位置的那个数;如果这组数的个数为偶数,则中位数是位于中间位置的两个数的平均值).
输入

该程序包含多组测试数据,每一组测试数据的第一行为N,代表该组测试数据包含的数据个数,1 <= N <= 15000.

接着N行为N个数据的输入,N=0时结束输入
输出

输出中位数,每一组测试数据输出一行

加载中
返回顶部
顶部