【题目】
有很多无序的数,从中找出最大的K个数。假定他们都不相等。
【解法一】
如果数据不是很多,例如在几千个左右,我们可以排一下序,从中找出最大的K个数。排序可以选择快速排序或者堆排序
-
#include<stdio.h>
-
#include<stdlib.h>
-
intcmp(constvoid*a,constvoid*b){
-
return*(int*)a-*(int*)b;
-
}
-
intmain(){
-
intn,k;
-
intNum[1000];
-
while(scanf("%d%d",&n,&k)!=EOF){
-
-
for(inti=0;i<n;i++){
-
scanf("%d",&Num[i]);
-
}
-
-
qsort(Num,n,sizeof(Num[0]),cmp);
-
-
for(i=n-k;i<n;i++){
-
printf("%d",Num[i]);
-
}
-
printf("\n");
-
}
-
return0;
-
}
【解法二】
我们可以继续对上面的算法进行优化,我们只是从这些无序的数中选出最大的K个数,并不需要前K个数据有序,也不需要后N-K个数据有序。
怎样才能避免做后N-K个数据有序呢?
回忆一下快速排序,快排中的每一步,都是将待排数据分做两组,其中一组的数据的任何一个数都比另一组中的任何一个大,然后再对两组分别做类似的操
作,然后继续下去……在本问题中,假设 N 个数存储在数组 S 中,我们从数组 S 中随机找出一个元素 X,把数组分为两部分 Sa 和 Sb。
Sa 中的元素大于等于 X,Sb 中元素小于 X。这时,有两种可能性:
1. Sa中元素的个数小于K,Sa中所有的数和Sb中最大的K-|Sa|个元素(|Sa|指Sa中元素的个数)就是数组S中最大的K个数。
2. Sa中元素的个数大于或等于K,则需要返回Sa中最大的K个元素。
这样递归下去,不断把问题分解成更小的问题,平均时间复杂度 O(N *log2K)。
-
#include<stdio.h>
-
#include<stdlib.h>
-
-
intPartition(inta[],intlow,inthigh){
-
inti,j,index;
-
i=low;
-
j=high;
-
-
index=a[i];
-
while(i<j){
-
-
while(a[j]<index&&i<j){
-
j--;
-
}
-
-
if(i<j){
-
a[i]=a[j];
-
i++;
-
}
-
-
while(a[i]>=index&&i<j){
-
i++;
-
}
-
-
if(i<j){
-
a[j]=a[i];
-
j--;
-
}
-
}
-
a[i]=index;
-
returni;
-
}
-
intKBig(inta[],intlow,inthigh,intk){
-
intindex,n;
-
if(low<high){
-
-
index=Partition(a,low,high);
-
n=index-low+1;
-
-
if(n==k){
-
returnindex;
-
}
-
-
elseif(n<k){
-
returnKBig(a,index+1,high,k-n);
-
}
-
-
else{
-
returnKBig(a,low,index,k);
-
}
-
}
-
}
-
-
intmain(){
-
inta[]={4,5,1,6,2,7,3,8};
-
for(i=0;i<=KBig(a,0,7,6);i++){
-
printf("%d",a[i]);
-
}
-
printf("\n");
-
return0;
-
}
【解法三】
用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X,如果X比堆顶元素Y小,则不需要改变原来的堆,因为这个元素比最大的K个数要小。如果X比堆顶元素大,那么用X替换堆顶元素Y,在替换之后,X可能破坏了最小堆的结构,需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。
当数据量很大时(100亿?这时候数据已经不能全部装入内存,所以要求尽可能少的遍历数组)可以采用这种方法。
-
#include<stdio.h>
-
#include<stdlib.h>
-
-
-
-
intMinHeap(inta[],intindex,intk){
-
intMinIndex=index;
-
-
intLeftIndex=2*index;
-
-
intRightIndex=2*index+1;
-
if(LeftIndex<=k&&a[LeftIndex]<a[MinIndex]){
-
MinIndex=LeftIndex;
-
}
-
if(RightIndex<=k&&a[RightIndex]<a[MinIndex]){
-
MinIndex=RightIndex;
-
}
-
-
-
inttemp;
-
if(MinIndex!=index){
-
-
temp=a[index];
-
a[index]=a[MinIndex];
-
a[MinIndex]=temp;
-
-
MinHeap(a,MinIndex,k);
-
}
-
return0;
-
}
-
-
-
-
intBuildMinHeap(inta[],intk){
-
inti;
-
-
for(i=k;i>=1;i--){
-
-
MinHeap(a,i,k);
-
}
-
return0;
-
}
-
-
intmain(){
-
intn=6;
-
intk=3;
-
-
inta[]={0,3,17,8,27,7,20};
-
-
BuildMinHeap(a,k);
-
-
for(inti=n;i>k;i--){
-
-
-
inttemp;
-
if(a[1]<a[i]){
-
-
temp=a[i];
-
a[i]=a[1];
-
a[1]=temp;
-
-
MinHeap(a,1,k);
-
}
-
}
-
for(i=1;i<=k;i++){
-
printf("%d",a[i]);
-
}
-
return0;
-
}
如果不明白堆的用法,可以参考:堆排序
堆排序中主要讲解最大堆,最大堆和最小堆几乎一样。自己看看就知道了。
【解法四】
这个方法受到一定的限制。
如果所有N个数都是正整数,而且取值范围都不太大。可以考虑申请空间,记录每个整数出现的次数,然后再从大到小取最大的K个。
-
#include<stdio.h>
-
#include<string.h>
-
-
constintMaxN=100;
-
intcount[MaxN];
-
-
intmain(){
-
intk=3;
-
inta[]={3,17,8,27,7,20};
-
memset(count,0,MaxN);
-
-
for(inti=0;i<6;i++){
-
count[a[i]]++;
-
}
-
-
intsumCount=0;
-
for(i=MaxN;i>=0;i--){
-
sumCount+=count[i];
-
if(sumCount>=k){
-
break;
-
}
-
}
-
-
intindex=i;
-
for(i=index;i<MaxN;i++){
-
if(count[i]>0){
-
printf("%d",i);
-
}
-
}
-
printf("\n");
-
return0;
-
}
分享到:
相关推荐
精易编程助手v2.5.rar
语言写的编程助手 v2.5
机器人编程 KEBA编程 Kemotion 应用及编程手册V2.5 版本新增的指令 MoveRobotAxis, PTPSearch, LinSearch, DOUT.Connet 的使用 方法,DOUT.Set 新功能
老版 ROBOLAB 2.5编程者指南,适用于rcx 1.0,具有很好的参考价值!
信捷 XC系列编程工具 版本2.5 2005年 信捷 XCP2.5 编程软件
对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1 行是1 个正整数a。第2 行是正整数k。 Output 程序运行结束时,将计算出的最小数输出到文件output.txt中。...
CONCEPT_2.5_编程软件文档说明
输入一个N位高精度的正整数,去掉其中任意K个数字后剩下的数字按原左右次序组成一个新的正整数。写算法对给定的N和K,寻找一种方案使得剩下的数字组成的新数最小。 输入:N、K以及一个N位高精度的正整数 输出:剩下...
本人收集的一点资料 希望能给大家带来帮助
Visual Foxpro 2.5 (VFP2.5) 简体中文版 of DOS,可做收藏、学习、研究。
最大K乘积问题: ...如果将I划分为k段,则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法,对于给定的I和k,求出I的最大k乘积。 编程任务: 对于给定的I 和k,编程计算I 的最大k 乘积。
协议1,协议2>@interface和类名中间一个空格类名后紧跟:之后空格加上父类协议之间用,空格分割@protocol的写法写法的模板@protocol协议的名称<协议1,协议2>@potocol和协议的名称有空格协议的名称和其他协议有空格...
PM2.5粉尘传感器相关内容测试代码程序C语言编程实现
计算机软件-编程源码-FOXPRO 2.5使用与参考大全.zip
松汇编是一个汇编语言集成开发环境,主要面向汇编语言初学者,也可以进行开发。除了普通的编辑功能以外,它还可以自动整理格式、高亮显示和编译、链接、调试汇编程序,并且提供语法元素导航的功能。调用TASM 5.0。...
fpw25b,是FOXPRO中文版2.5FOR WINDOWS,对早期系统编程是值得收藏的软件。
AGG的功能与GDI+的功能非常类似,但提供了比GDI+更灵活的编程接口,其产生的图形的质量也非常高(自称超过GDI+) 1.下载AGG库,它的家在http://www.antigrain.com,目前最高版本是AGG2.5 2.解压,后面以[AGG]表示AGG的...
python 2.5 实用编程工具
计算组合数,利用C语言编程,是最经典的C语言事例
商业源码-编程源码-Cmsez v2.5 Build 20051124 For Linux.zip