- 总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB
- 描述
-
给定一个数组，统计前k大的数并且把这k个数从大到小输出。
- 输入
-
第一行包含一个整数n，表示数组的大小。n < 100000。
第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。
第三行包含一个整数k。k < n。 - 输出
- 从大到小输出前k大的数，每个数一行。
- 样例输入
-
10 4 5 6 9 8 7 1 2 3 0 5
- 样例输出
-
9 8 7 6 5
分析：
按照快速排序的思想，把数组前k大的数放到数组末尾。然后在对数组末尾k个元素做排序再输出该部分元素。
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 int a[100010]; 5 6 int cmp(const void *a,const void *b) 7 { return (*(int *)a) - (*(int *)b); } 8 9 //将a[]数组下标区间[start,end]前k大的数放到数组下标在[start,end]范围的末尾部分. 10 void FindMaxK(int a[],int start,int End,int k) 11 { 12 if(start-End+1==k) return;//若是元素个数刚好就是k个，则可以直接返回. 13 int i=start,j=End,key=a[start]; 14 while(i<j) 15 { 16 while(i<j&&a[j]>=key) --j; 17 a[i]=a[j]; 18 while(i<j&&a[i]<=key) ++i; 19 a[j]=a[i]; 20 } 21 a[i]=key; 22 if(End-i+1==k) return;//数组后半段的元素个数为End-i+1,刚好够k个 23 else if( End-i+1 > k) FindMaxK(a,i+1,End,k);//数组后半段的元素个数多于k个 24 else FindMaxK(a,start,i-1,k-(End-i+1) );//数组后半段元素个数不够k个。所以要在前半段继续寻找k-（End-i+1）这么多个。 25 } 26 int main() 27 { 28 int n,k; 29 30 scanf("%d",&n); 31 for(int i = 0;i <n; ++i) scanf("%d",&a[i]); 32 scanf("%d",&k); 33 34 FindMaxK(a,0,n-1,k); 35 36 qsort(a+n-k,k,sizeof(a[0]),cmp); 37 for(int i = n-1;i >= n-k; --i) printf("%d\n",a[i]); 38 return 0; 39 }
C ++版：（北大郭炜老师）
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 int a[100010]; 7 8 void swap(int & a,int & b) 9 { int tmp = a; a = b; b = tmp; } 10 11 //将a[]数组下标区间[start,end]前k大的数放到数组下标在[start,end]范围的末尾部分. 12 void FindMaxK(int a[],int start,int End,int k) 13 { 14 if(start-End+1==k) return;//若是元素个数刚好就是k个，则可以直接返回. 15 int i=start,j=End,key=a[start]; 16 while(i<j) 17 { 18 while(i<j&&a[j]>=key) --j; 19 swap(a[i],a[j]); 20 while(i<j&&a[i]<=key) ++i; 21 swap(a[i],a[j]); 22 } 23 if(End-i+1==k) return;//数组后半段的元素个数为End-i+1,刚好够k个 24 else if( End-i+1 > k) FindMaxK(a,i+1,End,k);//数组后半段的元素个数多于k个 25 else FindMaxK(a,start,i-1,k-(End-i+1) );//数组后半段元素个数不够k个。所以要在前半段继续寻找k-（End-i+1）这么多个。 26 } 27 int main() 28 { 29 int n,k; 30 31 scanf("%d",&n); 32 for(int i = 0;i <n; ++i) scanf("%d",&a[i]); 33 scanf("%d",&k); 34 35 FindMaxK(a,0,n-1,k); 36 37 sort(a+n-k-1,a+n); 38 for(int i = n-1;i >= n-k; --i) 39 printf("%d\n",a[i]); 40 return 0; 41 }
本问题可以参考阅读：
http://www.cnblogs.com/macher/p/5317439.html
http://www.cnblogs.com/huashanqingzhu/p/6591091.html
