牛客周赛 Round 31 D.小红数组操作【哈希双链表+设置哨兵】

原题链接：https://ac.nowcoder.com/acm/contest/74362/D

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小红拿到了一个数组，初始数组为空，她希望你实现以下两种操作：

1. 输入1 x y，将x插入在元素y的右边。保证此时数组中没有元素等于x，且数组中存在一个y。特殊的，如果将x插入在数组的最左边，则y=0
2. 输入2 x，将元素x删除。
   请你在所有操作后输出整个数组。

输入描述:

第一行输入一个正整数q，代表操作次数。
接下来的q行，每行输入两个整数2 x或者三个整数1 x y，代表一次操作。操作含义如题目说明。
1≤q≤2×10^5
1≤x≤10^9
0≤y≤10^9

输出描述:

第一行输出一个整数n，代表最终数组的大小。
第二行输出n个正整数，代表最终的数组。

示例1

输入

4
1 2 0
1 7 2
1 1000 7
2 7

输出

2
2 1000

说明

第 1 次操作后，数组为[2]。
第 2 次操作后，数组为[2,7]。
第 3 次操作后，数组为[2,7,1000]。
第 4 次操作后，数组为[2,1000]。

解题思路：

题目一共有俩种操作，第一种操作是在某个元素y的右边插入一个元素x，第二种操作是删除元素x，首先快速的插入和删除这就是双链表的经典操作，但是我们的插入和删除是需要找到特定元素的位置再进行操作，我们肯定不能暴力的遍历一遍去查找，这个双链表我们可以使用哈希表来记录位置，这样就可以快速索引到特定元素的位置了，由于我们还可能在头部位置插入或者删除，由于我们操作过程的值是1<=val<=1e9，我们可以在头部设置哨兵结点0，刚好题目说了y==0时，是在头部插入，刚好我们设置的哨兵结点就是0号结点，在头部插入实际就是在0号结点右边插入，这样头部插入删除操作就和后面的结点一样了，不需要特殊考虑了，同时为了方便输出答案，我们可以在尾部设置哨兵结点N=1e9+1。

时间复杂度：双链表插入删除操作时间复杂度为O(n)，n表示操作的次数。

空间复杂度：哈希表l[x]记录x的左边是谁，哈希表r[x]记录x的右边是谁，空间复杂度为O(n)。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N=1e9+1;
int n,m;
unordered_map<int,int>l,r;
int main()
{
    cin>>n;
    int ans=0;
    //设置头部哨兵0,尾部哨兵1e9+1
    //那么0号结点右边是1e9+1,1e9+1左边是0号结点
    r[0]=N,l[N]=0;
    for(int i=0;i<n;i++)
    {
        int op,x,y;
        scanf("%d",&op);
        if(op==1){  //双链表插入操作
            scanf("%d%d",&x,&y);
            int left=y,right=r[y];
            l[x]=left,r[left]=x;
            r[x]=right,l[right]=x;
            ans++;
        }else {  //双链表删除操作
            scanf("%d",&x);
            r[l[x]]=r[x];
            l[r[x]]=l[x];
            ans--;
        }
    }
    cout<<ans<<endl;
    int pos=0;
    //尾部哨兵结点方便输出答案
    while(r[pos]!=N)printf("%d ",r[pos]),pos=r[pos];
    return 0;
}