C++STL库神器：nth_element() 详解

nth_element()

nth_element() 函数头文件：algorithm.h

功能介绍

arr[n];
//默认求第m大的元素
std::nth_element(arr, arr+m, arr+n);

//定义cmp可求第m小的元素
bool cmp(int a, int b){
	return a>b;
}
std::nth_element(arr, arr+m, arr+n, cmp);

注意

①、函数是将第 m 大的元素放在 arr 数组中适当位置，其他元素按照第 m 元素的大小划分。
在[ 0, n ]这个范围内，在第 m 个元素之前的元素都小于或等于第 m 个元素，而且第 m 个元素后面的每个元素都会比它大。

②、用户可自定义排序方式（第 m 大元素或第 m 小元素）。
算法默认将小于或等于第 m 的元素排在第 m 的元素的前面，大于第 m 的元素排在第 m 的元素后面。
用户可自定义排序方式，这个特性与sort函数相同。

③、nth_element()函数仅将第 m 大/小的数在 arr 数组中排好了位置，并不返回值。输出 arr[m] 即是第 m 大/小的数。

例题练习
输入 n(n<5000000 且 n 为奇数) 个数字 a_i(0<a_i<10⁹)，输出这些数字的第 k 小的数。最小的数是第 0 小。
洛谷测试平台

#include<cstdio>
#include<algorithm>
#include<string.h> 
#define ll long long
using namespace std;
ll arr[5000010];

int main(){
	int n, m;
	memset(arr, 0, sizeof(arr));
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++){
		scanf("%lld", &arr[i]);
	}
	nth_element(arr, arr+m, arr+n);
	printf("%lld", arr[m]);
	return 0;
}