P4305 [JLOI2011] 不重复数字——题解

解题思路

顺序扫描序列，用哈希集合记录已经出现过的值。插入成功说明是第一次出现，立即输出；插入失败说明已经出现，跳过即可。

复杂度分析

期望时间复杂度 $O(n)$，额外空间复杂度 $O(n)$。

易错点

输出顺序必须保持第一次出现的先后次序，不能简单排序后去重。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin>>T;
    while(T--){
        int n; cin>>n;
        unordered_set<int> seen;
        bool first=true;
        for(int i=0;i<n;i++){
            int x; cin>>x;
            if(seen.insert(x).second){
                if(!first) cout<<' ';
                cout<<x; first=false;
            }
        }
        cout<<'\n';
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin>>T; while(T--){ int n; cin>>n; unordered_set seen; bool first=true; for(int i=0;i<n;i++){ int x; cin>>x; if(seen.insert(x).second){ if(!first) cout<<' '; cout<<x; first=false; } } cout<<'\n'; } return 0; }