一道绿题的做题记录（P4305）

· · 个人记录

做了一道题，就是这道

一看到这题我就想用桶排了，但“给出的数在 32 位有符号整数范围内”开不了这么大的桶。于是想到了用set。

翻了翻set的函数，了解了大致用法，但是，问题来了：怎么查询set中的元素？想了想，只能用指针了。但是我并没有系统地学习过指针，只能按我看到的，一步一步来了。

代码是这样的。

#include<bits/stdc++.h>
using namespace std;
int t,n,k;
set <int> z;
int main()
{
    cin>>t;
    for(int az=0;az<t;az++)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>k; 
            z.insert(k);
        } 
        set <int> ::iterator c=z.begin();
        while(c!=z.end())
        {
            cout<<*(c)<<" ";
            c++;
        }
        z.clear();
        cout<<endl;
    }
    return 0;
}

点击编译，芜湖！编译成功！（这就是蒟蒻吗）然后输入了示例数据，发现不太对：怎么数据被排序了。

仔细翻了下书，发现“set容器内的元素会被自动排序”

好吧，无事发生。

又翻了下书，发现了find()函数。那既然这样，我直接输进来时find一下有没有，有就跳过，没有就插入再输出不就OK了？我真是个小天才

于是有了这样的代码

#include<bits/stdc++.h>
using namespace std;
int t,n,k;
set <int> z;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);//快读，不加少对两个点
    cin>>t;
    for(int az=0;az<t;az++)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>k; 
            if(z.find(k)==z.end())
            {
                z.insert(k);
                cout<<k<<" ";
            } 

        } 
        z.clear();
        cout<<endl;
    }
    return 0;
}

然而TLE两个点。

说实话那个时候纳闷了半天，想着这不都O(n)了吗？这也太离谱了。最后看着大佬Rainbow_sjy❤OI的题解打了一遍，总算是过了。

代码：

/***************************

本代码需要在C++11环境下运行，否则编译失败 

***************************/
#include<bits/stdc++.h>
//#include<unordered_map>
using namespace std;
inline int read()
{
    char c=getchar();
    int x=0,f=1;
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+c-48;
    return x*f;
}
int t,n,x;
unordered_map<int,bool> s;
void work()
{
    s.clear();
    n=read();
    for(int i=1;i<=n;i++)
    {
        x=read();
        if(!s[x])
        {
            printf("%d ",x);
            s[x]=1;
        }
    }puts("");
}
int main()
{
    t=read();
    while(t--)work();
    return 0; 
}

想了想，这不跟我的思路一样吗？然后继续翻书，发现“set搜索、移除和插入拥有对数复杂度”，“unordered_map的底层采用哈希表的实现，查询的时间复杂度为是O(1)”。

好家伙，无事发生。

总结：不仅要熟悉各种数据结构的用法，还有性质。 同样，还有指针雾

话说，这是本蒟蒻过的第一道绿题