1 条题解
-
0
首次出现档案:解题说明
用
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
- 上传者