寻找第K大数
思考题
给定N个数，求其中第K大的数。
查找第K大 CSU 2078
小W有很强的好胜心，也有很明确的目标，总是希望当第k名，但是小W太菜了，经常达不到目标，于是他每次考试后都想知道第k名的分数是多少，然后以它为目标。 现在给出了每个人的分数，请求编程能力很强的你帮他迅速找到第k名的分数为多少，这样他才有更多的时间去学习。
第一行为一个正整数t代表有t组数据。每组数据第一行为两个正整数n和k，第二行为n个正整数。 1 <= k <= n <=10^7
对于每组数据，输出第k大的数
input
1
6 2
1 2 3 4 5 6
output
5
方法1：快排中的二分思想
时间复杂度时O(n)， 大概最快的解决方法了。
找一个基准数，把比它大的放在左边，比它小的放在右边。如果最终该数数所在 位置刚好是第k个，那么它就是答案。否则只需要在该数组的左半部分找，或者右半部分找。
实现方法就是利用快速排序的原理，以此达到二分查找的目的。另外由于此题数量级比较高1e7，输入必须要用“读入挂”。代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
///读入挂(大量数据时，比scanf都快好几倍)
namespace fastIO
{
#define BUF_SIZE 100000
bool IOerror = 0;
inline char nc()
{
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if ( p1 == pend )
{
p1 = buf;
pend = buf + fread( buf, 1, BUF_SIZE, stdin );
if ( pend == p1 )
{
IOerror = 1;
return(-1);
}
}
return(*p1++);
}
inline bool blank( char ch )
{
return(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t');
}
inline void rd( int &x )
{
char ch;
while ( blank( ch = nc() ) )
;
if ( IOerror )
return;
for ( x = ch - '0'; (ch = nc() ) >= '0' && ch <= '9'; x = x * 10 + ch - '0' )
;
}
#undef BUF_SIZE
};
using namespace fastIO;
/**
以上是copy的读入挂代码，codeblocks可能运行不会报错，但是不支持，但是 oj 上面提交妥妥的。
只能用来输入整数，使用方法是
int a;
rd(a);
**/
using namespace std;
const int N = 1e7 + 5;
int a[N];
int main()
{
int t;
rd(t);
while(t--){
int n , k;
rd(n); rd(k);
for(int i = 0; i < n; i++){
rd(a[i]);
}
//拟快排
for(int l = 0 , r = n-1; l <= r; ){///样例：1 \n 5 3 \n 1 2 3 4 5 这种情况，最终i,j相等的时候，也需要进行一次循环。
int i = l, j = r;
int temp = a[l];
while(i < j){
while(i < j && a[j] <= temp) j--; a[i] = a[j];//此处以a[i]为中间变量将a[j] , a[i]两者值进行了交换。
while(i < j && a[i] >= temp) i++; a[j] = a[i];
}
a[i] = temp;//基准数移到中间位置。实际上此时a[l]已经被改变，但是对此题目来说不影响结果。
if(i == k-1){printf("%d\n", a[k-1]); break;}//第K大的数，下标为k-1
else if(k-1 > i)l = i + 1;
else if(k-1 < i)r = i - 1;
}
}
return 0;
}
/**
耗时：888ms < 1s
Memory：41184 Kb
Accepted
codeblocks 不支持读入挂 ， 但 oj 支持。
**/
方法2：直接排序（肯定是超时妥妥的）
//经典冒泡排序
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5;
int a[N];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i = 0; i<n; i++){
scanf("%d", &a[i]);
}
//冒泡排序由大到小
for(int i = 0; i < n; i++){ //需要冒泡的次数
bool p = false; //加入布尔变量判断是否还需要继续比较
for(int j = 0; j < n-i-1; j++){ //进行冒泡，每个数和后一个数比较
if(a[j] < a[j+1]){
int t;
t = a[j], a[j] = a[j+1], a[j+1] = t;
p = true;
}
}
if(!p) break;
}
printf("第%d大的数为%d", k, a[k-1]);
return 0;
}
冒泡缺点很明显， 效率很低。
下面试一下直接快速排序+读入挂，然后输出第K大数。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <algorithm>
namespace fastIO
{
#define BUF_SIZE 100000
bool IOerror = 0;
inline char nc()
{
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if ( p1 == pend )
{
p1 = buf;
pend = buf + fread( buf, 1, BUF_SIZE, stdin );
if ( pend == p1 )
{
IOerror = 1;
return(-1);
}
}
return(*p1++);
}
inline bool blank( char ch )
{
return(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t');
}
inline void rd( int &x )
{
char ch;
while ( blank( ch = nc() ) )
;
if ( IOerror )
return;
for ( x = ch - '0'; (ch = nc() ) >= '0' && ch <= '9'; x = x * 10 + ch - '0' )
;
}
#undef BUF_SIZE
};
using namespace fastIO;
using namespace std;
const int N = 1e7+5;
int a[N];
int main()
{
int t;
rd(t);
while(t--){
int n , k;
rd(n); rd(k);
for(int i = 0; i < n; i++){
rd(a[i]);
}
sort(a , a+n);
printf("%d\n", a[n-k]);
}
return 0;
}
/**
直接快速排序，数量级太高
数量级1e7 , 时限1000ms
实际用时>2060ms(超出最大限制)
空间复杂度O(n)
**/
方法3：multiset容器的使用（依旧差了点，暴时）
思路：维护最大的K个数。先把前K个数读入数组，并且进行排序。然后，将剩下的元素在逐个读入。当新的元素被读到时，如果他小于数组的最小的元素则忽略，否则先删除数组中最小的元素，然后再将该元素放在数组的正确位置。
该方法需要做大量的排序、查询、删除、插入的操作，因此很容易想到使用集合set代替上面提到的数组， 但是由于set具有确定性，其中的元素不可重合。
有一种既有set的有序性，又可以存储可重复元素的容器——multiset。使用方法和set基本一致
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
namespace fastIO
{
#define BUF_SIZE 100000
bool IOerror = 0;
inline char nc()
{
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if ( p1 == pend )
{
p1 = buf;
pend = buf + fread( buf, 1, BUF_SIZE, stdin );
if ( pend == p1 )
{
IOerror = 1;
return(-1);
}
}
return(*p1++);
}
inline bool blank( char ch )
{
return(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t');
}
inline void rd( int &x )
{
char ch;
while ( blank( ch = nc() ) )
;
if ( IOerror )
return;
for ( x = ch - '0'; (ch = nc() ) >= '0' && ch <= '9'; x = x * 10 + ch - '0' )
;
}
#undef BUF_SIZE
};
using namespace fastIO;
using namespace std;
//可重复集合
multiset<int> a;
int main()
{
int t;
rd(t);
while(t--){
int n , k;
rd(n); rd(k);
for(int i = 0; i < n; i++){
int x;
rd(x);
if(a.size() < k)
a.insert(x);
else if(x > *(a.begin())){
a.erase(a.begin());
a.insert(x);
}
else
continue;
}
int i = k;
for(multiset<int>::iterator it = a.end(); i >= 0; it--, i--){
if(i == 0)
printf("%d\n", *it);
}
}
return 0;
}
/**
比直接用快排快了点，不过还是超时
用时：1998ms , 内存占用大：76000kb
另外：本地codeblocks 不能使用读入挂，似乎只有在oj上才能用。
**/
这种方法比直接快速排序快一点，但是还是不行。