nth_element函数原型有四个,详细我就不一一累赘了,我们就用最普通的用法寻找第k位置的元素。
函数用法为:nth_element(first,kth,end)。
first,last 第一个和最后一个迭代器,也可以直接用数组的位置。
kth,要定位的第k个元素,能对它进行随机访问.
将第k_th元素放到它该放的位置上,左边元素都小于等于它,右边元素都大于等于它.
例如:
1 vector<int> a(9);
2 for(int i = 0; i < 9; i++)
3 a[i] = i+1;
4 random_shuffle(a.begin(),a.end());
5 for(int i = 0; i < 9; i++)
6 cout << a[i] << " ";
7 cout << endl;
8
9 nth_element(a.begin(),a.begin()+4,a.end());
10 cout << *(a.begin()+4) << endl;
11
12 for(int i = 0; i < 9; i++)
13 cout << a[i] << " ";
14 cout << endl;
结果为:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL1UDO4YzM2QTMx0SO2YTNyQTMxETNwgDM4EDMy0iM3YDO0QTMvwFOwgTMwIzLcJzN2gDN0EzLcd2bsJ2Lc12bj5ycn9Gbi52YugTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
可以发现函数只是把kth的元素放在了正确位置,对其他元素并没有排序,所以可以利用这个函数快速定位第k个元素,当然,这个函数也支持你直接写比较函数,此处不再累赘因为ACM中基本不会用到。
那么为什么要选择这个函数呢,这就和复杂度有关了,nth_element的空间复杂度为O(1),在数据量大的时候时间复杂度为O(n),数据少的情况最坏为O(n^2),因为函数原理是随机访问,但实际运用过程中,基本都会是O(n)的时间复杂度。所以说是非常迅速的。