1 条题解
-
0
题目大意
给整数序列排序,再按长度的奇偶求中位数。
解题思路
用插入排序维护已排好序的前缀。取出下一个元素,将前缀中比它大的元素向右挪,再把它插入空出的位置。数组下标从 0 开始,奇数个时取
n / 2,偶数个时取n / 2 - 1和n / 2的平均值。最坏时间复杂度为 ,排序额外空间复杂度为 。主函数用长度上限为 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
- 上传者
吉公网安备22010402001496号