C++ STL 模板库中list应用题
小红数组操作
https://ac.nowcoder.com/acm/contest/74362/D
题目思路：要求两种操作，一种是插入，一种是删除，由于时间复杂度控制必须在On或者Onogn的情况下，询问次数已经是On的基础上，所以插入删除元素必须为O1或Ologn的时间复杂度，所以很容易想到只有哈希表或者map查找才能将复杂度降为O1，观察大佬代码用的list，经过学习，当知道确切位置的时候list的插入删除元素的时间复杂度为O1，这里的map的第二维存取的是第一维所指的位置的迭代器，方便list进行插入操作，而list里的next函数
的意思是找到此迭代器的下一个位置，list的insert操作的函数返回值所返回的是一个迭代器，
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N = 2e5 + 10;
int main() {
list<int> a;
map<int,list<int>::iterator> p;
int tt;
cin>>tt;
while(tt--) {
int op,x;
cin>>op>>x;
if(op==1) {
int y;
cin>>y;
if(y == 0) {
p[x] = a.insert(a.begin(), x); //insert返回一个插入新元素的迭代器
}else {
p[x] = a.insert(next(p[y]), x);
}
}else {
a.erase(p[x]);//删除迭代器所在的元素
p.erase(x);//删除map容器里的元素
}
}
cout<<a.size()<<'\n';
for(int x:a) cout<<x<<" ";
return 0;
}
/*
*/
阿里云成长空间 763人发布
投递哔哩哔哩等公司6个岗位