题目描述
给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第 k 小数。
数据范围
1≤n≤100000,
1≤k≤n
样例
输入样例:
5 3
2 4 1 5 3
输出样例:
3
算法1
STL中的 nth_element()
nth_element()算法应用的范围由它的第一个和第三个参数指定。第二个参数是一个指向第n个元素的迭代器。如果这个范围内的元素是完全有序的,nth_dement()的执行会导致第 n 个元素被放置在适当的位置。这个范围内,在第 n 个元素之前的元素都小于第n个元素,而且它后面的每个元素都会比它大。算法默认用<运算符来生成这个结果。
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include<iterator>
#include<functional>
#include<cstring>
#include<stack>
#include<map>
#include <iomanip>
#include <string>
#include <numeric>
#include <bitset>
#include<cctype>
#include<string>
#include<string.h>
#include<queue>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int a[1000005];
int main() {
int n,k;
cin >> n>>k;
for (int i = 0; i < n; i++)cin >> a[i];
nth_element(a, a + k-1, a+n);
cout << a[k-1] << " ";
return 0;
}