中位数计数的问题,要求使用C语言来实现,怎么实现?

Problem Description
中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。

现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。

Input
多组测试数据

第一行一个数n(n≤8000)

第二行n个数,0≤每个数≤109,

Output
N个数,依次表示第i个数在多少包含其的区间中是中位数。

Sample Input
5
1 2 3 4 5

Sample Output
1 2 3 2 1

2个回答

有个通用解法,求数组中的第k大数
方法是使用快排类似的思想,写个伪代码吧

findKindex(a[], start, end, k):
    tmp = a[len-1]
    index = partition(a,start, end, tmp);
    if(index == k)
        return a[index]
    if(index > k)
        return findKindex(a, start, index, k);
    else
        return findKindex(a, index+1, end, k - index)

这样无论是求中位数,即第len/2个数,还是其他任意第k个数,都可以在平均期望复杂度O(lg n)时间内找到

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
计数排序算法的C语言实现
以前看过网上的一篇关于一种号称时间复杂度能达到O(n)的不用比较就可以实现排序的算法——计数排序法,这是自己用C写的一个实现,大家可以参考下,欢迎指证。
51Nod1682 中位数计数【中位数】
1682 中位数计数 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。 现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。 Input 第一行一个数n(n<=8000) 第二行n个数,0
中位数计数
我竟然把中位数当成了平均数来算…… 这道题目坑点颇多(可能是我比较水吧)最后几组样例卡时间用map会超时,用数组的话尽量开的大一些(2倍反正是够了),而且数组定义的位置不同可能连样例都过不了 int ans,pos=0,cnt[8005<<1]; //memset(cnt,0,sizeof(cnt)); cnt[8005]
数字图像处理-编程实现染色体计数 C语言实现
实验内容: 对于下面这幅图像,编程实现染色体计数,并附简要处理流程说明。 处理步骤: 1. 读取图像,转换为灰度图像 平滑滤波去噪 图像二值化 对图像进行膨胀 再次膨胀(视情况而定) 腐蚀(视情况而定) 反转 统计连通区域个数并输出 保存图像。 void main() { Bitmap *bmp = (Bitmap *)malloc(sizeof(Bitmap));// bui
八皇后 c语言实现 方法计数
有问题给我发评论或留言 交流也可以给我发邮件 499830474@qq.com
字符串计数 C语言实现 ACM习题
字符串计数 C语言实现 ACM习题
使用C语言实现
使用HMAC-SHA256和HMAC-SHA1加密算法对报文进行加密。
HDU5701 中位数计数【中位数+水题】
中位数计数 Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2125    Accepted Submission(s): 735 Problem Description 中位数定义为所有值从小到大排序后排在正中间的那个
使用栈来实现符号平衡----c语言实现
使用栈来实现符号平衡—-c语言实现用栈比较容易实现的应用:符号平衡 源码如下:#include <stdio.h> #include <malloc.h> /* 编程思路:为实现符号平衡,先创建一个空栈,先读入一对符号 的左边,直到读入这对符号的右边,把符号弹出,如果这对符号 对称则继续,直到最后符号全部读完,并且栈为空。 */ struct node { char symbol;
怎么在C语言,使用指针实现冒泡排序?
怎么在C语言,使用指针实现冒泡排序?
中位数(C语言)
Description 计算有限个数的数据的中位数的方法是:把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数,则中间那个数据就是这群数据的中位数;如果数据的个数是偶数,则中间那2个数据的算术平均值就是这群数据的中位数。 现在给出n个正整数,求他们的中位数。 Input 第一行:n —— 数列数字的个数(1 。 第二行:有n个正整数,每两个数中间用空格隔
c语言中位数
一个课程用的小程序,排序实现查找数组中的中位数
图书管理系统C语言实现(代码+要求)
1、 图书借阅查询系统 要求: (1)定义合适的结构体对图书信息进行描述(至少包括作者、图书名称、出版社、可借状态等); (2)能够进行模糊查询(输入一个关键字,在相关信息中包含关键字的要能够查询,比如,在图书作者中输入“朱”,则作者名中包含“朱”字的要都能查询出来)、综合查询(可以设置多个查询条件,查询同时满足条件的记录)。 (3)能进行图书的借还操作。
怎么用SQL来实现以下要求?
rn 有一个数据表A记录如下:rnrn 编号 户名 委托户名 小计 rn 1 市政府文明办 市政府 78rn 1 市政府行政处 市政府 22rn 2 市委统战部 市委 10rn 2 市委经济工作部 市委 20rn 3 酒厂 酒厂 15rnrn 要求生成一个按编号来汇总的数据表Brnrn 编号 户名 委托户名 小计 rn 1 市政府文明办 市政府 100rn 2 市委统战部 市委 30rn 3 酒厂 酒厂 15rnrn rn 注意:一定要生成一个数据表B,并且B中有编号,户名,委托户名,小计字段rnrn rnrn
高级要求,大家来看看怎么实现
我们的项目组长要求我们作这样一个东西:rn一个计算函数单独写在一个文件里面,比如:c.csrn要有如下特性:rn1.可以被其他页面调用(这个好说,关键是下面的)rn2.函数里面的参数不是由外面传入的而是直接写在文件里面的(其实就成了常量)(这个似乎也没什么问题)rn3.要写另一个页面,里面有几个输入框和一个按钮,输入框里面输入新的参数值再按这个按钮就可以更改上面这个包含计算函数的文件c.cs,使里面的参数变成新的值....rnrn各位高手,能给点思路么?我怎么也想不出该怎么去动态改文件...
C语言实现使用动态数组实现循环队列
我在上一篇博客《C语言实现使用静态数组实现循环队列》中实现了使用静态数组来模拟队列的操作。由于数组的大小已经被指定,无法动态的扩展。所以在这篇博客中,我换成动态数组来实现。动态数组可以不断开辟内存空间,只是会在数组的初始化时有所不同,其他对数组的操作都是一样的。代码上传至 https://github.com/chenyufeng1991/Queue_DynamicArray 。(1)声明变量st
C语言怎么实现多任务的?
用习惯了汇编的时间片轮,突然想起来,C怎么实现的呢?rn要求不多高,假如按键,LED,数码管,红外解码要求同时处理rn怎么解决这个问题的?继续在中断设标志然后片轮任务吗?rn还是说有什么好的解决办法呢?rn单片机而已,没有操作系统的任务调配。rn请指教一下,thx。
C语言怎么实现小波变换?
一副尺寸为N*N大小的256级灰色图像矩阵A(数据类型为unsigned char),对其进行DWT分解(离散小波变换),要求得到分解后的四个子图矩阵A0,A1,A2,A3,用C语言如何描述?以及用四个子图A0,A1,A2,A3如何重构A?
C语言怎么实现定时器
C语言怎么实现定时器 比如我现在要3分钟执行一次我的函数 怎么做。
使用c语言实现注释转换
使用c语言实现注释转换,只要是将c注释转换为c++注释 整体思路 首先,我们需要两个文件,分别存放注释转换前的代码(input.c)和转换后的代码(output.c) 之后,我们对注释转换过程中的出现的几种状态进行分析,得出几种状态之间相互的关系 同时,我们需要对注释转换过程中出现的几种问题进行分析 //1.一般情况 int i = 0 //2.换行问题 /*int ...
使用C语言实现字符串分割
之前分享了一篇使用C++(std::string 作为容器)进行字符串分割的博文: https://blog.csdn.net/r5014/article/details/82802664   现在又想用C语言做一个字符串分割的函数,大概功能是这样: 需要分割的字符串“    this is a charactor  raw.    ” 使用 ' '分割 分割之后会返回一个char** ...
HDU 5701 中位数计数
Problem Description 中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。 现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。   Input 多组测试数据 第一行一个数n(n≤8000) 第二行n个数,0≤每个数≤109,  
HDU5701-中位数计数
中位数计数                                                                            Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)                              
hdu_5701_中位数计数
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5701 题意:不解释 题解:n^2的方法:sum[j]表示当前枚举的数到第j个数形成的区间里当前数偏离中位数的程度。cnt[k]表示偏离程度为k的次数,由于k可能为负,所以预先加上n。这里我们先向右扫描,记录cnt,再向左,当a[j]>a[i],则加1,否则减1。向左扫的时候,ans加上之前相同偏离
中位数计数 51Nod - 1682
中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。Input第一行一个数n(n&amp;lt;=8000) 第二行n个数,0&amp;lt;=每个数&amp;lt;=10^9OutputN个数,依次表示第i个数在多少包含其的区间中是中位数。Sample Input5 1 2 3 4 5...
51Nod-1682-中位数计数
ACM模版描述题解这里,我们可以分析得到,符合规则的区间有四种形式,分别是:// i (1) // j---i (2) // i---j (3) // j'--i--j" (4)而这里,第一种不用过多处理,就是1;第2种和第3种类似,所以,我们需要求出来i之前的num的匹配情况,和i之后的num的匹配情况;而第四种要求的是,在第2种和第3种的基
HDU-5701-中位数计数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5701     Problem Description 中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。 现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。   Input 多组测试数据 第一行一
中位数计数 (思维 + 技巧)
中位数计数Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1610 Accepted Submission(s): 583Problem Description 中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个
51nod 1682 中位数计数
1682 中位数计数  基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。 现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。   Input 第一行一个数n(n&amp;lt;=8000) 第二行n个...
HDU-5701 中位数计数(水题)
中位数计数 Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2608 Accepted Submission(s): 852 Problem Description 中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数...
51nod-1682 中位数计数
原题链接 1682 中位数计数 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。 现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。
hdu 5701 中位数计数
中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。 现在有nn个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。 Input 多组测试数据 第一行一个数n(n≤8000)n(n≤8000) 第二行nn个数,0≤0≤每个数≤109≤109, Output NN个数,依次表示第ii个数在多少包含其的区间中是中位数。
hdu 中位数计数
                                            中位数计数 Time Limit : 12000/6000ms (Java/Other)   Memory Limit : 65536/65536K (Java/Other) Total Submission(s) : 11   Accepted Submission(s) : 5 Problem Des...
使用c语言实现单链表
该文件是我最近闲来无事实现的链表的方法,包括增加,删除,显示等功能,希望对刚接触或者忘记的同学们能起到复习和快速入门的作用
使用C语言实现队列
#include &amp;lt;stdio.h&amp;gt;#include &amp;lt;malloc.h&amp;gt;typedef struct queue_node { struct queue_node* prev; struct queue_node* next; void *p;//节点的值} node;// 表头static node *phead = NULL;static int count = 0;...
使用C语言实现单链表
List.h文件 #ifndef __LIST_H__ #define __LIST_H__ #include #include #include typedef int Data; typedef struct List { Data arrary; struct List* next; }List; List* BuyList(Data x);
使用C语言实现串口通信
串口发送接收程序,使用于使用串口发送或接收数据的场合。
使用c语言实现图的遍历
实现图的创建 打印一个有向图 深度优先遍历 广度优先遍历 希望对大家有帮助啊
使用c语言实现文件传输
使用c语言技术实现文件传输
hdoj 5071 中位数计数
思维题bzoj原题。。。 枚举每个点补充,把每个点的左前缀和右前缀的大于它减小于它的差的情况都搞出来就行了不超时。。。 为什么感觉百度之星第二场比第一场题更适合我然而。。。都是天意啊#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define MAXN 17005 #define MID 8100 u
相关热词 c# stream 复制 android c# c#监测窗口句柄 c# md5 引用 c# 判断tabtip 自己写个浏览器程序c# c# 字符串变成整数数组 c#语言编程写出一个方法 c# 转盘抽奖 c#选中treeview