1 条题解

  • 0
    @ 2026-11-11 20:37:50

    题目大意

    给整数序列排序,再按长度的奇偶求中位数。

    解题思路

    用插入排序维护已排好序的前缀。取出下一个元素,将前缀中比它大的元素向右挪,再把它插入空出的位置。数组下标从 0 开始,奇数个时取 n / 2,偶数个时取 n / 2 - 1 和 n / 2 的平均值。最坏时间复杂度为 O(n2)O(n^2),排序额外空间复杂度为 O(1)O(1)。主函数用长度上限为 1000 的数组读入数据。

    易错点

    易错点 说明
    在原序列中直接取中间项 先按非降序排列所有数。
    整数除法丢掉小数部分 用 2.0 作除数。
    两个中间值相加溢出 在做加法之前把其中一个转为 double。

    填空答案

    第 1 空

    先排序,再按元素个数的奇偶返回中位数。

    for (int i = 1; i < n; ++i) {
            int current = values[i];
            int j = i;
            while (j > 0 && values[j - 1] > current) {
                values[j] = values[j - 1];
                --j;
            }
            values[j] = current;
        }
    
        if (n % 2 != 0) {
            return values[n / 2];
        }
        return ((double)values[n / 2 - 1] + values[n / 2]) / 2.0;
    

    第 2 空

    将数组和元素个数传给 Median,把返回的 double 交给 printf。

    Median(values, n)
    

    参考代码

    #include <stdio.h>
    
    double Median(int values[], int n) {
        for (int i = 1; i < n; ++i) {
            int current = values[i];
            int j = i;
            while (j > 0 && values[j - 1] > current) {
                values[j] = values[j - 1];
                --j;
            }
            values[j] = current;
        }
    
        if (n % 2 != 0) {
            return values[n / 2];
        }
        return ((double)values[n / 2 - 1] + values[n / 2]) / 2.0;
    }
    
    int main(void) {
        int n, values[1000];
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &values[i]);
        }
        printf("%.2lf\n", Median(values, n));
        return 0;
    }
    
    • 1

    信息

    ID
    650
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    156
    已通过
    25
    上传者