nth_element
位于<algorithm>中的 nth_element 函数可以用O(n) 的复杂度快速查找第 K 大的数,用法详见代码。
/*Copyright: Copyright (c) 2018
*Created on 2018-11-04
*Author: 十甫
*Version 1.0
*Title: STL-nth_element
*Time: ?? mins
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int size = 100005;
int n, num[size];
int main() {
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", &num[i]);
}
int k;
scanf("%d", &k);
nth_element(num + 1, num + k, num + 1 + n);
for(int i = 1;i <= n;i++) {
printf("%d ", num[i]);
}
printf("\n");
return 0;
}