- 总时间限制: 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个元素做排序再输出该部分元素。
#include<stdio.h>
#include<stdlib.h> int a[]; int cmp(const void *a,const void *b)
{ return (*(int *)a) - (*(int *)b); } //将a[]数组下标区间[start,end]前k大的数放到数组下标在[start,end]范围的末尾部分.
void FindMaxK(int a[],int start,int End,int k)
{
if(start-End+==k) return;//若是元素个数刚好就是k个，则可以直接返回.
int i=start,j=End,key=a[start];
while(i<j)
{
while(i<j&&a[j]>=key) --j;
a[i]=a[j];
while(i<j&&a[i]<=key) ++i;
a[j]=a[i];
}
a[i]=key;
if(End-i+==k) return;//数组后半段的元素个数为End-i+1,刚好够k个
else if( End-i+ > k) FindMaxK(a,i+,End,k);//数组后半段的元素个数多于k个
else FindMaxK(a,start,i-,k-(End-i+) );//数组后半段元素个数不够k个。所以要在前半段继续寻找k-（End-i+1）这么多个。
}
int main()
{
int n,k; scanf("%d",&n);
for(int i = ;i <n; ++i) scanf("%d",&a[i]);
scanf("%d",&k); FindMaxK(a,,n-,k); qsort(a+n-k,k,sizeof(a[]),cmp);
for(int i = n-;i >= n-k; --i) printf("%d\n",a[i]);
return ;
}
C ++版：（北大郭炜老师）
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std; int a[]; void swap(int & a,int & b)
{ int tmp = a; a = b; b = tmp; } //将a[]数组下标区间[start,end]前k大的数放到数组下标在[start,end]范围的末尾部分.
void FindMaxK(int a[],int start,int End,int k)
{
if(start-End+==k) return;//若是元素个数刚好就是k个，则可以直接返回.
int i=start,j=End,key=a[start];
while(i<j)
{
while(i<j&&a[j]>=key) --j;
swap(a[i],a[j]);
while(i<j&&a[i]<=key) ++i;
swap(a[i],a[j]);
}
if(End-i+==k) return;//数组后半段的元素个数为End-i+1,刚好够k个
else if( End-i+ > k) FindMaxK(a,i+,End,k);//数组后半段的元素个数多于k个
else FindMaxK(a,start,i-,k-(End-i+) );//数组后半段元素个数不够k个。所以要在前半段继续寻找k-（End-i+1）这么多个。
}
int main()
{
int n,k; scanf("%d",&n);
for(int i = ;i <n; ++i) scanf("%d",&a[i]);
scanf("%d",&k); FindMaxK(a,,n-,k); sort(a+n-k-,a+n);
for(int i = n-;i >= n-k; --i)
printf("%d\n",a[i]);
return ;
}
本问题可以参考阅读：
http://www.cnblogs.com/macher/p/5317439.html
http://www.cnblogs.com/huashanqingzhu/p/6591091.html