题解 | 数据流中的中位数

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num int整型 
 * @return 无
 */

int data[1000]; // 数据范围n≤1000，数组大小设为1000足够
int count = 0;  // 记录当前数据流中的元素个数

void Insert(int num) {
    // 边界保护：最多存储1000个元素
    if (count >= 1000) {
        return;
    }
    
    // 找到插入位置：第一个比num大的元素的下标（升序排列）
    int insert_pos = count; // 默认插入到末尾
    for (int i = 0; i < count; i++) {
        if (data[i] > num) {
            insert_pos = i;
            break;
        }
    }
    
    // 将插入位置后的元素后移一位，腾出空间
    for (int j = count; j > insert_pos; j--) {
        data[j] = data[j - 1];
    }
    
    // 插入新元素
    data[insert_pos] = num;
    count++; // 元素个数+1
}

/**
 * 获取当前数据流的中位数
 * @return 中位数（偶数个时返回平均值，奇数个时返回中间值）
 */
double GetMedian() {
    // 无数据时返回0（题目保证n≥1，可省略此判断）
    if (count == 0) {
        return 0.0;
    }
    
    // 奇数个元素：返回中间位置的数
    if (count % 2 == 1) {
        int mid = count / 2;
        return (double)data[mid];
    } 
    // 偶数个元素：返回中间两个数的平均值
    else {
        int mid1 = count / 2 - 1;
        int mid2 = count / 2;
        return (data[mid1] + data[mid2]) / 2.0;
    }
}