完整题目描述:
Problem Description
一天,萌萌的妹子--瑶瑶(tsyao)很无聊,就来找你玩。可是你们都不知道玩什么。。。尴尬了一阵子,机智的瑶瑶就提议:“这样吧,你说N个整数xi,然后在随意说一个数字k,我能够快速地说出这些数字里面第 k 大的数字。”
Input
第1行 两个整数N, K以空格隔开;
第2行 有N个整数(可出现相同数字,均为随机生成),同样以空格隔开。
0 < n ≤ 5*10^6 , 0 < k ≤ n
1 ≤ xi ≤ 10^8
Output
Sample Input
5 2 5 4 1 3 1
Sample Output
4
Hint
一开始看到这道题的时候,我用的是快排,先排序然后直接输出“第K大”的那个数,很明显,这样做的话超时了,时间限制是2秒,而数据量高达500W(快排每秒排序的数据量大概在100W),所以我后来百思不得其解,在Acdream搜到这道题目之后就到百度看了下题解,发现这道题主要是对快排进行了优化。因为这道题是要找第K大的数字,很明显,如果我们对所有的数字进行排序的话,不必要的操作实在是太多了。所以我们这里要联想到快排排序的思想,快速排序每次排序一个数(即将“基准数”排序到升序或者降序后这个数在数组中所在的位置),所以,我们找第K大的数字的话,就只需要用降序快速排序算法,如果当前的“基准数”下标大于K-1的时候,那么我们只需要继续排序当前“基准数”左边的序列即可,反之则排序当前“基准数”右边的序列。当排序的“基准数”到第K-1个数的时候,然后程序马上终止,返回并输出这个数,这样的话节省了很多不必要的排序操作。核心代码:
if(k-1 == i) return a[i];
else if (k - 1 < i) quick_sort(left,i - 1,a);
else if (k - 1 > i) quick_sort(i + 1,right,a); //排序基准数左边和右边的序列
后来继续去看了这道题的题解,发现这道题除了快排优化之外,还可以继续优化,因为这道题的数据量非常大,所以,这道题可以在读入操作时进行“读入优化”。
读入优化操作:
int input()
{
int ans=0;
char a;
while((a=getchar())<'0'||a>'9');
ans=a-'0';
while((a=getchar())>='0'&&a<='9')
{
ans=ans*10+a-'0';
}
return ans;
}
这样的话,在大量数据读入的时候会比scanf读入数据快的多一点,这个其实和scanf(“%d”,&n); 是等价的,但是实验证明这个是要更快一点的。
然后这道题还有另外的做法就是利用STL中内置的函数:
nth_element函数
使用方法:nth_element(start, start+n, end)
使第n大元素处于第n位置(从0开始,其位置是下标为n的元素),并且比这个元素小的元素都排在这个元素之前,比这个元素大的元素都排在这个元素之后,但不能保证他们是有序的。
注意这是升序排序下的结果,因此调用这个函数的时候核心代码为:
nth_element(num,num+n-k,num + n);
这样的话第K大元素正好就位于数组中倒数第几个位置。附上这道题两种方法的源代码:
//降序快速排序,每次都以最左边的数字作为基准数
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
using std::vector;
using std::cout;
int quick_sort(int left,int right,vector <int> &a);
int input(); //读入优化
int n,k;
int main()
{
int ans;
while(scanf("%d%d",&n,&k) == 2 && n && k)
{
vector <int> num(n);
for(int i = 0;i < n;i++)
num[i] = input();
ans = quick_sort(0,n-1,num);
printf("%d\n",ans);
}
return 0;
}
int input()
{
int ans=0;
char a;
while((a=getchar())<'0'||a>'9');
ans=a-'0';
while((a=getchar())>='0'&&a<='9')
{
ans=ans*10+a-'0';
}
return ans;
}
int quick_sort(int left,int right,vector <int> &a) //优化,减少排序次数
{
int temp,i,j; //用来存储基准数
temp = a[left]; //每次都以最左边的数字作为基准数
if(left > right) return a[left-1];
i = left;
j = right;
while(i < j)
{
while(i < j && a[j] <= temp)
j--;
while(i < j && a[i] >= temp)
i++;
if(i < j)
{
int flag = a[j];
a[j] = a[i];
a[i] = flag;
}
}
a[left] = a[i];
a[i] = temp; //基准数归位
if(k-1 == i) return a[i];
else if (k - 1 < i) quick_sort(left,i - 1,a);
else if (k - 1 > i) quick_sort(i + 1,right,a); //排序基准数左边和右边的序列
}
2.利用STL内置的nth_element函数
#include<cstdio>
#include<algorithm>
int num[5000005];
using std::nth_element;
int main()
{
int n,k;
while(scanf("%d%d",&n,&k) == 2 && n && k)
{
for(int i = 0;i < n;i++)
scanf("%d",&num[i]);
nth_element(num,num+n-k,num + n);
printf("%d\n",num[n-k]);
}
return 0;
}
如有错误,还请指正,O(∩_∩)O谢谢