P4305 [JLOI2011] 不重复数字

zcbiao / 2023-06-17 / 原文

题目：

思路：新建一个数组或者哈希表，检查新输入的元素是否在里面，如果在就pass，如果不在就作为新元素存进去，最后输出即可

数组实现：60分,时间复杂度O（n^2）,或者O（nlogn）;

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int num;
    cin>>num;
    for(num;num>=1;num--)
    {
    int n,x;
    cin>>n;
    int j=0;
    int arry[n];
    for(int i=1;i<=n;i++)
    {
        int flag=0;
        cin>>x;
        for(int p=0;p<j;p++)//可以改为二分查找（时间复杂度为log（n)），不过也过不了
        {
            if(x == arry[p]) flag=1;
        }
        if(flag == 0)
        {
            arry[j]=x;
            j++;
        }
        
    }
    for(int y=0;y<j;y++)
    {        
        cout<<arry[y]<<' ';
    }
    cout<<'\n';
    }
    return 0;
}

哈希表实现：需要pause输，100分,时间复杂度O（n）

#include<bits/stdc++.h>
#define Iopause ios::sync_with_stdio(false), cin.tie(0),cout.tie(0) ;
using namespace std;


void Solve(){
    unordered_map <int ,int> hashtable;
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        auto it=hashtable.find(x);//关键在这，hashtable.find()的时间复杂度为O(1);
        if( it==hashtable.end() ){
            cout<<x<<' ';
            hashtable[x]=0;
        }
    
    }
    cout<<'\n';
    
    
}
int main()
{
    Iopause;
    int t;
    cin>>t;
    while(t--){
        Solve();
    }
    return 0;
}