首页 > 其他分享 >STL-algorithm(ACM)

STL-algorithm(ACM)

时间:2023-06-11 22:45:40浏览次数:47  
标签:begin 排序 end algorithm STL 位置 ACM int include

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

标签:begin,排序,end,algorithm,STL,位置,ACM,int,include
From: https://www.cnblogs.com/ACYee/p/17473785.html

相关文章

  • BouncyCastle
    在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务参考附件内容完成SM2加解密的内容,提交运行结果截图(10‘)2完成SM3,SM4算法的调用,提交运行结果截图和代码(15’,选做)BouncyCastle配置1.jar包下载官网:https://www.bouncycastle.org/latest_releases.htmlbcprov-e......
  • STL-string(ACM)
    1.相当于加了一些操作的vector<char>基本操作字符串转换(C++11)//将字符串转换为整型stoi()//将字符串转换为longlongstoll()//将字符串转换为float型stof()//将字符串转换为double型stod()后面加入s+=t;//时间复杂度O(t)s.push_back();字符串替换......
  • STL-multiset(ACM)
    1.与set不同的是,multiset可以允许多个相同元素同时出现重载函数(默认)multiset<int,int>mu;基本操作mu.erase(x);//把所有与x相同的元素删除//如果我们只想删除一个的话//通过删除迭代器实现mu.erase(mu.find(x));mu.count(x);//查的时间与x的个数有关,慎用需......
  • BouncyCastle
    任务详情在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务参考附件内容完成SM2加解密的内容,提交运行结果截图(10‘)完成SM3,SM4算法的调用,提交运行结果截图和代码(15’,选做)BouncyCastle配置1.jar包下载官网:https://www.bouncycastle.org/latest_releases.html......
  • STL-map(ACM)
    1.不存在的元素查询时会自动生成2.map就是一堆pair的集合,按照T1的字典序进行排列3.可以像vector那样根据下标随时访问重载函数 map<T1,T2>m;//下标的类型,值的类型//按照T1的值进行字典序排序//下方为赋值操作map<string,string>m;m["AC"]="Yee";m["Red"]=......
  • STL之Stack与queue的模拟实现与duque的底层结构(3千字长文详解)
    STL之Stack与queue的模拟实现与duque的底层结构设计模式的概念设计模式像是古代的兵法,是以前的人总结出来的一些在特定的情况下,某种特定的好用的方法总结STL中迭代器也是一种设计模式——==迭代器模式==STL中stack和queue的实现就是使用了一种设计模式——==适配器模式!==适......
  • STL之优先级队列(堆)的模拟实现与仿函数(8千字长文详解!)
    STL之优先级队列(堆)的模拟实现与仿函数优先级队列的概念优先队列是一种==容器适配器==,根据严格的弱排序标准,==它的第一个元素总是它所包含的元素中最大的==。本质就是一个堆!此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。......
  • STL之反向迭代器的实现
    反向迭代器的实现反向迭代器介绍反向迭代器和正向迭代器的区别就是反向迭代器的++/--是倒着走!那么反向迭代器的本质是什么?——==是一个容器适配器!==本质就是通过==封装迭代器==,来让其实现我们想要的行为!也可以通过通过复制一份正向迭代器,然后修改正向迭代器的行为,来实现反......
  • STL实践指南
    这是一篇指导您如何在Microsoft Visual Studio下学习STL并进行实践的文章。这篇文章从STL的基础知识讲起,循序渐进,逐步深入,涉及到了STL编写代码的方法、STL代码的编译和调试、命名空间(namespace)、STL中的ANSI / ISO字符串、各种不同类型的容器(container)、......
  • algorithm库的使用
    算法库(algorithm)1.什么是algorithm?algorithm库装满了好用的库函数,一般由#include<algorithm>包含。可是本蒻蒻还是喜欢万能头(逃2.经典的库函数(1)sort()函数sort(begin,end,cmp);这个函数有一些技术含量,但它只需要传入两个指针或随机迭代器(begin和end)和cmp比较......