STL-Notes-Vector

Sort

AC

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
   
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    vector<int> v;
    int n,num;
    cin>>n;
    while(cin>>num)
    {
   
        v.push_back(num);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++)
    {
   
        cout<<v[i]<<" ";
    }
    return 0;
}

Notes

  • vector v;创建int型的vector数组,其他类型同理
  • sort(v.begin(),v.end());使用sort函数对vector数组排序
  • v.push_back(); 向vector末尾添加元素

Erase

AC

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
   
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    vector<int> v;
    int n,nums,pos,a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
   
        cin>>nums;
        //join to vector
        v.push_back(nums);
    }
    cin>>pos;
    //add the arange 
    cin>>a>>b;
    //remove eles;
    v.erase(v.begin()+(pos-1));
    v.erase(v.begin()+(a-1),v.begin()+(b-1));
    //output ths answer;
    cout<<v.size()<<endl;
    for(int i=0;i<v.size();i++)
    {
   
        cout<<v[i]<<" ";
    }
    return 0;
}

Notes

  • v.erase(v.begin()+1,v.end()+3);从第一个开始删除到第2个
  • 左闭右开区间
  • v.erase(int position);删除指定位置的元素

Lower Bound

AC

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
   
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    vector<int> v;
    vector<int> Q;
    int n,x,q,y;
    cin>>n;
    for(int i=0;i<n;i++)
    {
   
        cin>>x;
        v.push_back(x);
    } 
    cin>>q;
    for(int i=0;i<q;i++)
    {
   
        cin>>y;
       int index = lower_bound(v.begin(),v.end(),y)-v.begin();
       if(v[index]==y)
       {
   
           cout<<"Yes"<<" "<<index+1<<endl;
       }
       else
       {
   
           cout<<"No"<<" "<<index+1<<endl;
       }
    }
    return 0;
}

Notes

  • 升序排序数组中

  • lower_bound( begin,end,target);

  • 从数组的begin位置到end-1位置二分查找第一个大于或等于target的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

  • upper_bound( begin,end,target);

  • 从数组的begin位置到end-1位置二分查找第一个大于target的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

提前阅读更多内容,请移步个人博客:XiaoYi的博客