欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

备战NOIP——STL复习1

程序员文章站 2022-03-23 09:18:54
...

 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;
}