题解 | #数据流中的中位数#

数据流中的中位数

http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

C语言求数据流中的中位数

解题思路

在数据流的输入时,维护一个递增序列,使用插入排序进行维护 然后计算中位数

 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param num int整型 
 * @return 无
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
//定义一个全局的变量 记录插入元素
static int array[1000];
static int arr_top=0;
void Insert(int num ) {
    // write code here
    //每次插入 进行插入排序 插入到合适的位置
    //保证插入的顺序是有序的
    int i=0;
    //第一个元素直接插入
    if(arr_top==0){
        array[arr_top]=num;
    }
    else{
        i=arr_top-1;
        while(num<array[i]&&i>=0){
            array[i+1]=array[i];
            i--;
            }
        array[i+1]=num;
    }
    arr_top++;
}
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return double浮点型
 */
double GetMedian() {
    // write code here
    double ans=0;
    
    if(arr_top%2)
        ans=array[arr_top/2];
    else
        ans=((double)array[arr_top/2]+(double)array[arr_top/2-1])/2;
    return ans;
}
全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务