1 前言

近期學(xué)習(xí)K-D Tree，用到了nth_element，然而不是很確定具體的用法
然而，在網(wǎng)上搜索、點(diǎn)了幾篇博客要么寫的不是很清楚，要么干脆直接是錯的
于是這篇博客用來記錄我個人對nth_element的理解，希望能對你有所幫助，如果我自己忘了也能看這篇博客記起來

2 相關(guān)信息

2.1 所需頭文件

#include<algorithm>

2.2 使用格式

有個一般式為：

nth_element(begin,nth,end,compare);

假設(shè)數(shù)組$a[]$的第1~m個位置有數(shù)，現(xiàn)在要求第n大
代碼如下

nth_element(a+1,a+n,a+m+1,cmp);

要注意的是，使用$nth\_element$需要事先using namespace std或者加std::
即有兩種選擇（可以見后面的代碼）

2.3 功能

對于一般的$sort$我們是在$\Theta (nlogn)$的時間復(fù)雜度內(nèi)使數(shù)組內(nèi)的元素有序，定義一個位置應(yīng)該有的值為排完序之后這個位置上的值
而$nt{h}_{e}lement$的作用就是在$\Theta (n)$的時間復(fù)雜度內(nèi)使得給定位置上的值成為這個位置該有的值（特殊的，在比較符號為小于并且起始位置為1的時候，做的是將數(shù)組中第n大的數(shù)放在n號位置）。
另外，$nth\_element$滿足做完后，所有其他位置的值與給定位置的值的相對大小關(guān)系一定符合（當(dāng)比較符號為小于的時候，相當(dāng)于說比第n大的數(shù)小的數(shù)都放在第n大的數(shù)前面，比第n大的數(shù)大的數(shù)都放在第n大的數(shù)后面）（是不是說的很繞，可以看后面代碼輸出時候的解釋）

2.3 實(shí)現(xiàn)

題目：輸入n,k,以及n個數(shù)，求這n個數(shù)中第k大的值
我們可以用這個題來驗(yàn)證$nt{h}_{e}lement$的功能

#include<cstdio> #include<algorithm> //using namespace std; int n,k,a[1000001]; int cmp(int a,int b){return a<b;} int main() {scanf("%d %d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);std::nth_element(a+1,a+k,a+n+1，cmp);//開頭的注釋掉了，那么這個地方要用用了std::for(int i=1;i<=n;i++)printf("%d ",a[i]);return 0; }

(注意，代碼中的cmp其實(shí)可以刪去，如果不傳cmp函數(shù)，默認(rèn)是“<”)
給出一組程序輸入輸出

你會發(fā)現(xiàn)，第3大的數(shù)3到了該去的位置，并且在3前面的數(shù)都比3小，在3后面的數(shù)都比3大

2.4 原理

眾所周知，$sort$主要的算法是快速排序
而$nth\_element$的本質(zhì)上就是快速排序的一部分
給出快排代碼

void sort(int*l,int*r) {if(l>=r)return;swap(*l,*(l+rand()%(r-l)));int *ll=l,*rr=r-1,v=*l;while(ll<rr){while(ll<rr&&(*rr)>=v)rr--;*ll=*rr;while(ll<rr&&(*ll)<=v)ll++;*rr=*ll;}*ll=v;sort(l,ll),sort(ll+1,r); }

$nth\_element$相當(dāng)于是給定了上面代碼的rand的值，然后不遞歸$sort$
由于太過簡單，就不貼代碼了

3 總結(jié)

容易發(fā)現(xiàn)，其實(shí)$nth\_element$并不難實(shí)現(xiàn)
但是STL的$nth\_element$速度尚可、使用方便
既然已經(jīng)封裝好了，不用白不用
學(xué)習(xí)一下使用方法能節(jié)省代碼量

總結(jié)

以上是生活随笔為你收集整理的nth_element的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。