一些好用的函数
前言:本篇主要简单记录一些平时遇到的好用的或者性能很特别的函数,持续更新中
1.关于全排列
(1)next_permutation()
头文件:
#include <algorithm>
函数原型:
bool next_permutation(iterator begin,iterator end)
用来求全排列的下一项(按字典序)
例:对于以下代码:
char ch[5]={'a','d','b','e','c'};
next_permutation(ch,ch+5);
cout << ch[0] << ch[1] << ch[2] << ch[3] << ch[4] << endl;
输出结果为:
adcbe
需要注意的是,这个函数返回值类型是\(bool\),当数组已经完全倒序时,函数会返回\(false\),根据这一原理,我们可以利用一个do-while
循环,对一个按字典序排列好的数组进行全排列的遍历:
char ch[3]={'a','b','c'};
do{
cout << ch[0] << ch[1] << ch[2] << endl;
}while(next_permutation(ch,ch+3));
注意这里一定要用do-while
,否则不会有原先的排列顺序
输出结果为:
abc
acb
bac
bca
cab
cba
(2)prev_permutation()
头文件:
#include <algorithm>
函数原型:
bool prev_permutation(iterator begin,iterator end)
用来求全排列的上一项(按字典序)
与上面的next_permutation()
类似,对于以下代码:
char ch[5]={'a','d','b','e','c'};
prev_permutation(ch,ch+5);
cout << ch[0] << ch[1] << ch[2] << ch[3] << ch[4] << endl;
输出结果为:
adbce
同理,当数组已经完全正序时,函数会返回\(false\),我们同样可以利用一个do-while
循环,对一个完全倒序的数组进行全排列的遍历:
char ch[3]={'c','b','a'};
do{
cout << ch[0] << ch[1] << ch[2] << endl;
}while(prev_permutation(ch,ch+3));
输出结果为:
cba
cab
bca
bac
acb
abc
2.关于二分查找
(1)lower_bound()
头文件:
#include <algorithm>
函数原型:
iterator lower_bound(iterator begin,iterator end,const T& val);
用来求单调不减序列\([begin,end)\)中第一个数值\(\geq val\)的迭代器,其中传入的参数\(begin\)和\(end\)分别为序列开头和末尾的迭代器,特别地,如果序列中所有数值都\(< val\),则会返回数组中下标为\(end\)的迭代器
例:对于以下代码
int a[5]={1,3,5,7,9};
cout << (lower_bound(a,a+5,1)-a) << " ";
cout << (lower_bound(a,a+5,2)-a) << " ";
cout << (lower_bound(a,a+3,8)-a) << " ";
cout << (lower_bound(a,a+5,10)-a) << endl;
输出结果为:
0 1 3 5
需要注意的是,这个函数内部实现利用了二分查找的原理,时间复杂度为\(O(\log n)\),所以并不需要手写二分查找函数
(2)upper_bound()
头文件:
#include <algorithm>
函数原型:
iterator upper_bound(iterator begin,iterator end,const T& val);
用来求单调不减序列\([begin,end)\)中第一个数值\(> val\)的迭代器,其中传入的参数\(begin\)和\(end\)分别为序列开头和末尾的迭代器,特别地,如果序列中所有数值都\(\leq val\),则会返回数组中下标为\(end\)的迭代器
例:对于以下代码
int a[5]={1,3,5,7,9};
cout << (upper_bound(a,a+5,1)-a) << " ";
cout << (upper_bound(a,a+5,2)-a) << " ";
cout << (upper_bound(a,a+3,8)-a) << " ";
cout << (upper_bound(a,a+5,10)-a) << endl;
输出结果为:
1 1 3 5
同理,这个函数内部实现也利用二分查找,时间复杂度\(O(\log n)\)
(3)equal_range()
头文件:
#include <algorithm>
函数原型:
pair<iterator,iterator> equal_range(iterator begin,iterator end,const T& val)
主要作用是在单调不减区间\([begin,end)\)内,寻找\(val\),返回值是一个\(pair\),\(first\)指向\(val\)的起始位置,\(second\)指向\(val\)的末尾之后的位置,特别地,如果序列内不含\(val\),会返回一个\(first\)和\(second\)都指向\(val\)应插入的位置
其实这个函数就是lower_bound()
和upper_bound()
的相加,\(pair\)的第一维就相当于lowerbound(begin,end,val)
的值,第二维相当于upperbound(begin,end,val)
的值
例:对于以下代码
int a[10]={1,2,2,3,3,3,5,5,7,7};
auto bounds=equal_range(a,a+10,3);
cout << bounds.first-a << " " << bounds.second-a << endl;
bounds=equal_range(a,a+10,4);
cout << bounds.first-a << " " << bounds.second-a << endl;
输出结果为:
3 6
6 6
同理,利用二分,时间复杂度\(O(n)\)
(4)binary_search()
头文件:
#include <algorithm>
函数原型:
bool binary_search(iterator start,iterator end,const T& val)
用来判断单调不减序列\([begin,end)\)中,是否存在\(val\),若存在,返回\(true\);若不存在,返回\(false\)
例:对于以下代码:
int a[5]={1,3,5,7,9};
if(binary_search(a,a+5,5)) cout << "Yes" << endl;
else cout << "No" << endl;
if(binary_search(a,a+5,6)) cout << "Yes" << endl;
else cout << "No" << endl;
输出结果为:
Yes
No
这个函数的内部实现同样利用了二分查找,时间复杂度\(O(\log n)\)
3.关于排序
(1)partial_sort()
头文件:
#include <algorithm>
函数原型:
void partial_sort(iterator begin,iterator middle,iterator end)
函数名称直译为“部分排序”,这个函数可以在无序的\([begin,end)\)区间内找到\((middle-begin)\)个最小的元素,并将它们置于数组的最前面,其余元素置于数组最后,但是要注意,其余元素的相对位置可能会改变,主要原因是内部实现利用大根堆进行比较
与sort()
函数一样,我们也可以自定义比较函数,传参时写在\(end\)之后,就能以自定义排序规则进行部分排序
例:对于以下代码
//自定义升序规则
bool cmp(int a,int b){return a>b;}
//以下在main函数中
int a[10];
srand(time(0));
for(int i=0;i<10;i++)
a[i]=rand()%100;
cout << "随机赋值后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
partial_sort(a,a+5,a+10);
cout << endl;
cout << "局部排序后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
partial_sort(a,a+10,a+10);
cout << endl;
cout << "全部排序后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
partial_sort(a,a+5,a+10,cmp);
cout << endl;
cout << "自定义局部排序后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
partial_sort(a,a+10,a+10,cmp);
cout << endl;
cout << "自定义全部排序后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
一组输出结果为:
随机赋值后,a数组如下:
49 16 36 52 17 83 60 51 14 27
局部排序后,a数组如下:
14 16 17 27 36 83 60 52 51 49
全部排序后,a数组如下:
14 16 17 27 36 49 51 52 60 83
自定义局部排序后,a数组如下:
83 60 52 51 49 14 16 17 27 36
自定义全部排序后,a数组如下:
83 60 52 51 49 36 27 17 16 14
值得一提的是,这个函数的时间复杂度为\(O(n\log m)\),其中\(n\)表示整个区间长度,\(m\)表示从\(begin\)到\(middle\)的长度,对于算法竞赛可能较慢,建议谨慎使用
(2)nth_element()
头文件:
#include <algorithm>
函数原型:
void nth_element(iterator begin,iterator middle,iterator end)
这个函数可以在无序的\([begin,end)\)区间内找到第\((middle-begin+1)\)小的数,并将其置于正确的下标为\((middle-begin)\)的位置,且所有小于等于这个数的都在其左边,大于等于这个数的都在其右边 (但不保证整个序列单调不下降)
例:对于以下代码:
int a[10];
srand(time(0));
for(int i=0;i<10;i++)
a[i]=rand()%100;
cout << "随机赋值后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
nth_element(a,a+4,a+10);
cout << endl;
cout << "找到下标为4的元素后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
一组输出结果为:
随机赋值后,a数组如下:
61 83 9 62 41 13 92 51 95 42
找到下标为4的元素后,a数组如下:
42 13 9 41 51 61 92 83 95 62
值得一提的是,这个函数的时间复杂度为\(O(n)\),其中\(n\)为序列长度,在无序序列中求第\(k\)小(大)等类似题目中是比较优秀的时间复杂度,与上面的partial_sort()
函数相比,nth_element()
函数可能可以处理更多的实际问题
(3)stable_sort()
头文件:
#include <algorithm>
函数原型:
void stable_sort(iterator begin,iterator end)
与sort()
函数类似,这个函数也是对\([begin,end)\)区间内的序列进行排序(默认升序)
但是这两个函数的不同点是:sort()
函数的内部实现主要依靠快速排序的思想,还外加了插入排序和堆排序,而stable_sort()
函数的内部实现依靠归并排序的思想,它能保证排序后相同元素的相对位置不改变,是一种稳定排序,但是相比而言,sort()
函数比stable_sort()
函数时间复杂度要低一些
同理,我们也可以自定义比较函数,与sort()
函数一样传入参数,使其按照自定义的排序规则排序
(4)is_sorted()
C++11的新函数,算法竞赛勿用
头文件:
#include <algorithm>
函数原型:
bool is_sorted(iterator begin,iterator end)
这个函数会判断\([begin,end)\)区间内序列是否有序(默认判断是否升序),若已有序返回\(true\),反之返回\(false\),特别地,如果序列内只有\(1\)个元素,也会返回\(true\)
同理,我们也可以自定义比较函数传入参数,使其按照自定义的排序规则判断是否有序
内部实现是\(for\)循环暴力判断相邻两个是否有序,时间复杂度\(O(n)\)
4.关于序列操作
(1)fill()
头文件:
#include <algorithm>
函数原型:
void fill(iterator begin,iterator end,const T& val)
主要作用是将序列内\([begin,end)\)区间内的值全部赋为\(val\)
(其实就是省个for循环而已)
例:对于以下代码
int a[10];
srand(time(0));
for(int i=0;i<10;i++)
a[i]=rand()%100;
cout << "随机赋值后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
fill(a,a+5,111);
cout << endl;
cout << "填充前五个元素为111后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
一组输出结果为:
随机赋值后,a数组如下:
29 54 83 2 68 79 71 6 81 55
填充前五个元素为111后,a数组如下:
111 111 111 111 111 79 71 6 81 55
(2)fill_n()
头文件:
#include <algorithm>
函数原型:
void fill_n(iterator begin,const T& count,const T& val)
主要作用是将序列内从\(begin\)开始,长度为\(count\)的区间内的值全部赋为\(val\)
(其实也还是省个for循环而已)
例:对于以下代码
int a[10];
srand(time(0));
for(int i=0;i<10;i++)
a[i]=rand()%100;
cout << "随机赋值后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
fill_n(a,5,111);
cout << endl;
cout << "填充前五个元素为111后,a数组如下:" << endl;
for(int i=0;i<10;i++)
cout << a[i] << "\t";
一组输出结果为:
随机赋值后,a数组如下:
38 37 14 27 10 57 61 3 85 29
填充前五个元素为111后,a数组如下:
111 111 111 111 111 57 61 3 85 29
(3)unique()
头文件:
#include <algorithm>
函数原型:
iterator unique(iterator begin,iterator end)
主要作用是把一个有序数组去重,并返回首个不重复的元素的迭代器
0条评论