一、作用

查找第n小的元素

二、用法

nth_element(起始地址，查找元素的下標(biāo)，最后一個元素地址+1)；
nth_element(起始地址，查找元素的下標(biāo)，最后一個元素地址+1，自定義排序)；

舉例：
查找數(shù)組中第6小的元素

#include<iostream> #include<algorithm>//必要頭文件 using namespace std; int main(){int a[10]={1,5,6,3,9,2,8,7,4,10};nth_element(a,a+5,a+10);//查找數(shù)組第6小的元素 cout<<"第6小的數(shù)是："<<a[5];//第6小的數(shù)放在了相應(yīng)的第6個位置了 } //console: //第6小的數(shù)是：6

那么能不能查找第n大的元素呢？
當(dāng)然可以的，將第n大的問題轉(zhuǎn)換為求第m小的問題就可以了
例如一個數(shù)組有10個元素，求第2大的數(shù)，那么它等同于求第10-2+1=9小的元素

#include<iostream> #include<algorithm>//必要頭文件 using namespace std; int main(){cout<<"請問您需要查找第幾大的數(shù)？" <<endl;int n;cin>>n; int a[10]={1,5,6,3,9,2,8,7,4,10};nth_element(a,a+10-n,a+10);cout<<"第"<<n<<"大的數(shù)是："<<a[10-n]; } //console: //請問您需要查找第幾大的數(shù)？ //2 //第2大的數(shù)是：9

自定義排序：
假如遇到無法直接比較大小的結(jié)構(gòu)體怎么辦呢？重載運(yùn)算符是一種辦法，也可以自定義排序，例：

#include<iostream> #include<vector> #include<algorithm>//必要頭文件 using namespace std; struct node{int x,y; // 構(gòu)造函數(shù) node(int x,int y){this->x=x;this->y=y;} }; bool cmp(node n1,node n2){return n1.x<n2.x; } int main(){vector<node> v;node n1(1,3);node n2(5,2);node n3(3,6);node n4(2,6);node n5(4,4);v.push_back(n1);v.push_back(n2);v.push_back(n3);v.push_back(n4);v.push_back(n5);nth_element(v.begin(),v.begin()+1,v.end(),cmp);cout<<"按x排序，第2小點(diǎn)的數(shù)是："<<endl;cout<<"x:"<<v[1].x<<' '<<"y:"<<v[1].y; }

函數(shù)的實現(xiàn)

與快速排序思路大致相同，例如一個數(shù)組有10個元素：4，3，9，1，8，6，5，10，2，7；

找第7小的元素：
第一步：開找第一個數(shù)，4，比4小的放在4左邊，比4大的放在4右邊
結(jié)果:3，1，2，4，9，8，6，5，10，7
結(jié)論：那么4是第4小的數(shù)，因為有3個比它小的元素在左邊

第二步：第7小的元素肯定在4的右邊，找4右邊的第一個數(shù)，9，比9小的放在9左邊，比9大的放在9右邊
結(jié)果:3，1，2，4，8，6，5，7，9，10
結(jié)論：那么9是第9小的數(shù)，因為有8個比它小的元素在左邊

第三步：第7小的元素肯定在9的右邊，找9左邊的第一個數(shù)，7，比7小的放在7左邊，比7大的放在7右邊
結(jié)果:3，1，2，4，6，5，7，8，9，10
結(jié)論：那么7是第7小的數(shù)，因為有6個比它小的元素在左邊

得到第7小的數(shù)7，結(jié)束

時間復(fù)雜度平均為O(n),最差為O(n^2);
它把不必要的排序步驟省略掉了，復(fù)雜度大大降低

總結(jié)

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

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