1.next_permutation
next_permutation(a+1,a+n+1) 用于求解a数组的下一个较大的排列。
prev_permutation则与之相反,求解下一个较小的排列。
函数参数均为数组起始坐标,和终止坐标,如果存在下一个排列,则返回1,否则返回0,同时把该数组变为下一个排列。
应用前景广泛。
实例代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define ull unsigned long long
#define N 10
#define M number
using namespace std;
int n,a[N];
inline void print(){
for(int i=1;i<=n;i++) printf("%d ",a[i]);
printf("\n");
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) a[i]=i;
print();
while(next_permutation(a+1,a+n+1)) print();
// while(prev_permutation(a+1,a+n+1)) print();
return 0;
}
2.nth_element
作用:求解第k小的数,并保证,第k大的数在第k位,前k个数均比这个数小,后面的数均大于等于这个数
参数 nth_element(a+1,a+k+1,a+n+1,cmp)
其中的意思为,在1到n这个区间的数组a中,把第k大的数放在第k位(相当于1来说),前面的数均比它小,后面的数均比它大。cmp为自定义比较函数。 nth_element默认是越小优先级越高。我们通过类似于sort的自定义函数,可以改变其优先级。
事件负责度\(O(n)\),相当于用快速排序。比sort一遍要优。
代码:
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a, int b){
return a > b;
}
int main()
{
int a[10] = {0,4,7,6,9,1,8,2,3,5};
int b[10] = {0,4,7,6,9,1,8,2,3,5};
int c[10] = {0,4,7,6,9,1,8,2,3,5};
nth_element(a+1,a+3,a+10);
//将下标为2,也就是第3个数放在正确的位置
//也就是求的是第3小
cout <<"第3小是:"<< a[3] << endl;
for(int i = 1; i < 10; i++)
cout << a[i] << " "; puts("");//注意下标是从0開始计数的
//那么求第3大,就是求第9-3+1小,即第7小
//也就是将下标为6的第7个数,放在正确的位置
nth_element(b+1,b+7,b+10);
cout <<"第3大是:"<< b[7] << endl;
for(int i = 1; i < 10; i++)
cout << b[i] << " "; puts("");//注意下标是从0開始计数的
nth_element(c+1,c+3,c+10,cmp);//第一种方法
//nth_element(c,c+2,c+9,greater<int>()); //第二种方法
cout <<"第3大是:"<< c[3] << endl;
for(int i = 1; i < 10; i++)
cout << c[i] << " "; //注意下标是从0開始计数的
}
https://blog.csdn.net/sugarbliss/article/details/88050145