1 条题解

  • 0
    @ 2026-11-16 20:48:26

    首次出现档案:解题说明

    用 unordered_set<long long> 保存已经遇到的编号,同时用 vector<long long> 保存答案顺序。从左到右扫描;seen.insert(x).second 为 true 时,说明 x 首次出现,立即 push_back(x) 到答案。

    扫描每个位置后,集合恰好包含此前出现过的编号,答案向量按首次出现的时间记录它们,因此得到要求的顺序。集合只负责判重,输出顺序来自向量。

    配合 reserve,期望总时间 O(n),空间 O(n)。若使用 set 判重而依然用向量记录顺序,时间 O(n log n) 也可行。

    常见错误:直接遍历哈希集合输出,集合遍历顺序不是输入顺序;改用 set 输出而把编号排序;每次都向答案追加造成重复。

    验证期望由独立 Python 算法生成,不读取参考程序。样例先手算,再以空实现确认测试失败;正式数据包含边界、固定种子随机及两个最大规模用例。

    C++17 参考实现

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n; cin>>n;
        unordered_set<long long> seen; seen.reserve(2*n+1);
        vector<long long> order; order.reserve(n);
        for(int i=0;i<n;++i) {
            long long x; cin>>x;
            if(seen.insert(x).second) order.push_back(x);
        }
        cout<<order.size()<<'\n';
        for(size_t i=0;i<order.size();++i) cout<<(i?" ":"")<<order[i];
        cout<<'\n';
        return 0;
    }
    
    
    • 1

    信息

    ID
    5269
    时间
    2000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者