unique(a.begin(), a.end()) 待研究 与离散化有关
//
翻转(reverse(位置,位置))
reverse(a.begin(), a.end()); int a[5] = {1, 2, 3, 4, 5}; reverse(a, a + 5); // 结果 5 4 3 2 1
循环移位(rotate(移动到该位置前一个地方,移动区间的头位置,移动的尾位置))
第一个位置必须在第二个位置(头位置)之前:只能从后边移位到前边去
int a[5] = {1, 2, 3, 4, 5}; rotate(a, a + 2, a + 5); for (int x : a) { cout << x << endl; } // 结果 3 4 5 1 2
排序
sort(a.begin(), a.end()); // 经典,待研究
返回 最小元素 / 最大元素 的 迭代器
vector<int> v{2, 1, 3, 5, 4}; auto it = min_element(v.begin(), v.end()); printf("%d\n", *it); it = max_element(v.begin(), v.end()); printf("%d", *it); // 结果 1 5
返回 >= / > 二分查找类型 的迭代器
lower_bound(); upper_bound(); // 这个只能用于vector等数组类型,map、set需用自带的
归并排序算法
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()) // 将a, b两个有序元素列归并排序后放入c中, 注意a, b要有序
归并排序算法(同空间)
inlace_merge(a.begin(), a.begin() + k, a.end()); // a.begin() + k 是前半部分最后一个元素 + 1 的位置 // 提示:inplace_merge比merge要慢 // 该算法是将原空间内的两个有序序列归并排序,不占额外空间
返回 下一个排列组合
next_permotation(); // next_permutation()会取得[first,last)所标示之序列的下一个排列组合, // 如果没有下一个排列组合,便返回false;否则返回true
使用例子
1、输出序列{1,2,3,4}字典序的全排列
#include <iostream> #include<algorithm> using namespace std; int main(int argc, char** argv) { int a[4]={1,2,3,4}; sort(a,a+4); do{ //cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl; for(int i=0;i<4;i++) cout<<a[i]<<" "; cout<<endl; }while(next_permutation(a,a+4)); return 0; }
2、输入任意一个字符串,输出其字典序的全排列
#include <iostream> #include<algorithm> using namespace std; int main(int argc, char** argv) { string str; cin>>str; sort(str.begin(),str.end()); do{ cout<<str<<endl; }while(next_permutation(str.begin(),str.end())); return 0; }
3、能否直接算出集合{1, 2, ..., m}的第n个排列?
举例说明:如7个数的集合为{1, 2, 3, 4, 5, 6, 7},要求出第n=1654个排列。
#include <iostream> #include<algorithm> using namespace std; int main(int argc, char** argv) { int a[7]={1,2,3,4,5,6,7}; sort(a,a+7); int n=0; do{ if(n==1654){ for(int i=0;i<7;i++) cout<<a[i]; cout<<endl; break; } n++; }while(next_permutation(a,a+7)); return 0; }
返回 上一个排列组合
prev_permotation();
快速查找第k位置上的元素
nth_element(a+l,a+k,a+r); // 第k个位置会放第k大的元素,k元素前是不排序的随机比k小, // k后是不排序的随机比k大的
nth_element的空间复杂度为O(1),在数据量大的时候时间复杂度为O(n),数据少的情况最坏为O(n^2),因为函数原理是随机访问,但实际运用过程中,基本都会是O(n)的时间复杂度。所以说是非常迅速的
标签:begin,排序,end,algorithm,STL,位置,ACM,int,include From: https://www.cnblogs.com/ACYee/p/17473785.html