BM48. 数据流中的中位数
描述
示例1
输入:
[5,2,3,4,1,6,7,0,8]
输出:
"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明:
数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...示例2
输入:
[1,1,1]
输出:
"1.00 1.00 1.00 "
C 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-02-09
//快排
// void _sord(int* nums, int left, int right){
// if(left>=right) return;
// int l=left, r=right, val=nums[left];
// while(l<r){
// while(l<r && nums[r]>val) r--;
// if(l<r) nums[l++]=nums[r];
// while(l<r && nums[l]<val) l++;
// if(l<r) nums[r--]=nums[l];
// }
// nums[l]=val;
// _sord(nums, left, l-1);
// _sord(nums, l+1, right);
// }
static int input[1000];
int pos=0;
void Insert(int num ) {
// write code here
if(pos==0 || input[pos-1]<=num) input[pos++]=num;
else{//input[pos-1]>num 插入
for(int i=0;i<pos;++i){//5,2
if(num<input[i]){
for(int j=pos;j>i;--j){
input[j] = input[j-1];
}
input[i]=num;
break;
}
}
pos++;//+1
}
// for(int i=0;i<pos;++i){
// printf("%d ", input[i]);
// }
}
double GetMedian() {
// write code here
// _sord(input, 0, pos-1);
if(pos%2){//奇数
return (double)input[pos/2];
}
return (double)(input[pos/2-1]+input[pos/2]) / 2;
// return 1.0;
}
C 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-07-18
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型
* @return 无
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
static int s[1000]={0};
static int len=0;
void Insert(int num ) {
// write code here
int i=0;
if(len==0){
s[len]=num;
}
else{
i=len-1;
while(i>=0 && s[i]>num){
s[i+1]=s[i];
i--;
}
s[i+1]=num;
}
len++;
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param 无
* @return double浮点型
*/
double GetMedian() {
// write code here
if(len%2!=0){
return s[len/2]*1.0;
}
else
return (s[len/2]+s[len/2-1])/2.0;
}
C 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2021-11-26
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型
* @return 无
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#define MAX_SIZE 1000
static double val[MAX_SIZE]={0.0};
static int len = 0;//当前长度
void Insert(int num ) {
int i,j;
if(len>=MAX_SIZE-1){
return;
}
if(len == 0){
val[len] = num;
len++;
return;
}
i=0;
while(i<=len){
if(i==len){
val[len] = num;
len++;
return;
}
if(num >= val[i]){
++i;
}else{
for(j=len; j>i; j--){
val[j] = val[j-1];
}
val[i] = num;
len++;
return;
}
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param 无
* @return double浮点型
*/
double GetMedian() {
int middle;
if(0==len){
return -1.0;
}
middle = len >> 1;
if(len & 0x01){
return val[middle];
}else{
return (val[middle]+val[middle-1])/2;
}
}
C 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-02-09
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型
* @return 无
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
static int len = 0;
int buffer[1000];
void Insert(int num ) {
// write code here
if(len>1000) return;
int i,j,key;
if(len==0){
buffer[len++] = num;
}
//直接插入排序
else{
key = num;
for(j=len-1; j>=0 && buffer[j]>key; j--){
buffer[j+1] = buffer[j];
}
buffer[j+1] = key;
len++;
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param 无
* @return double浮点型
*/
double GetMedian() {
// write code here
//若len为奇数
if(len & 0x01){
return buffer[len/2]*1.0;
}
else{
return (buffer[len/2-1]+buffer[len/2])*1.0/2;
}
}
C 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2021-12-22
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型
* @return 无
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#define MAX_SIZE 1000
static double val[MAX_SIZE] = {0.0};
static int len = 0;
void Insert(int num ) {
// write code here
int i, j;
if(len>=MAX_SIZE-1)
return;
if(len==0)
{
val[len]=num;
len++;
return;
}
i=0;
while(i<=len)
{
if(i==len)
{
val[len]=num;
len++;
return;
}
if(num>=val[i])
{
++i;
}
else
{
for(j=len;j>i;j--)
{
val[j]=val[j-1];
}
val[i]=num;
len++;
return;
}
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param 无
* @return double浮点型
*/
double GetMedian() {
// write code here
int middle;
if(0==len)
{
return -1.0;
}
middle =len>>1;
if(len&0x01)
return val[middle];
else
return (val[middle]+val[middle-1])/2;
}