526互联

STL-algorithm(ACM)

发布时间 2023-06-11 22:41:11作者: AC玴

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要慢
// 该算法是将原空间内的两个有序序列归并排序，不占额外空间

下面排列大佬博文

真大佬博文

排列算法STL简介

返回 下一个排列组合

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)的时间复杂度。所以说是非常迅速的