STL之nth_element用法

做题的时候遇到了一个有意思的问题

问:

给你一个序列让你求第k大数。

STL库里有直接可以对这个进行操作的函数，今天来梳理一下…

nth_element介绍

nth_element是一种部分排序算法。
返回值为void类型，返回部分排序后的原数组。

调用为:

1	nth_element(first, nth, last, camp);

其中，first和last是排序范围

camp是按什么顺序来比较。默认从小到大。

nth是排序的位置。术语叫做排序分区点.

并没有对原数组进行完全排序，只是把下标为nth的元素放在了正确的位置。

同时满足nth左边的元素都小于等于它，右边的元素都大于等于它。（默认升序）

//常用的几种形式
//1.求第k小数
nth_element(v.begin(), v.begin() + (k - 1), v.end())
//2.求第k大数
nth_element(v.begin(), v.begin() + (n - k), v.end(), greater<int>())
//3.求第k大数

两种情况：

求一个序列的第k小数

我们可以直接通过调用来完成，因为本身就是按照升序排列。

在这里我们需要注意如果使用容器或数组来进行时，下标的值如果从0开始，则我们求第k小数时，第k小数的下标是k - 1

示例 :

//求第k小数 k = 3 
//注意下标范围 nth_element中写下标位置 即为 k - 1
#include <bits/stdc++.h>

using namespace std;

int main(void) {
	vector <int> v;
	for(int i = 0; i <= 8; i++) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	nth_element(v.begin(), v.begin() + 2, v.end());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << v[2] << endl;
}

求一个序列的第k小数

同理，我们可以采用两种方案来解决

1.转换成序列按照升序排列利用$cmp$或greater()替换即可

示例:

//同理
//求第k大数 k = 3 
//注意下标范围 nth_element中写下标位置 即为 k - 1
#include <bits/stdc++.h>

using namespace std;

int main(void) {
	vector <int> v;
	for(int i = 0; i <= 8; i++) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	nth_element(v.begin(), v.begin() + 2, v.end(), greater<int>());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << v[2] << endl;
}

2.求第k大数即转换为求第$n - k + 1$小数。

此时下标为 n - k.即最后的数是$v[n - k]$

示例:

//写法1：
#include <bits/stdc++.h>

using namespace std;

int main(void) {
	vector <int> v;
	for(int i = 0; i <= 8; i++) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	int n = v.size();//利用转换
	nth_element(v.begin(), v.begin() + (n - 3), v.end());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << v[n - 3] << endl;
}
//写法2：
#include <bits/stdc++.h>

using namespace std;

int main(void) {
	vector <int> v;
	for(int i = 0; i <= 8; i++) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	int n = v.size();
	nth_element(v.begin(), v.end() - 3, v.end());
	for(int i = 0; i <= 8; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << v[n - 3] << endl;
}

nth_element介绍

参考资料