【题目来源】
https://www.luogu.com.cn/problem/P4305
【题目描述】
给定 n 个数，要求把其中重复的去掉，只保留第一次出现的数。
【输入格式】
第一行一个整数 T，表示数据组数。
对于每组数据，第一行一个整数 n。第二行 n 个数，表示给定的数。
【输出格式】
对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。
【输入样例】
2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6
【输出样例】
1 2 18 3 19 6 5 4
1 2 3 4 5 6
【说明/提示】
对于 30% 的数据，n≤100，给出的数 ∈[0,100]。
对于 60% 的数据，n≤10^4，给出的数 ∈[0,10^4]。
对于 100% 的数据，1≤T≤50，1≤n≤5×10^4，给出的数在 32 位有符号整数范围内。
【算法分析】
● STL unordered_set：https://cplusplus.com/reference/unordered_set/unordered_set/
unordered_set 是 C++ 标准库中的无序集合容器，基于哈希表实现。
#include <bits/stdc++.h>
using namespace std;int main() {unordered_set<int> ust= {1,3,5};auto x=ust.insert(2);if(x.second) {cout<<"Insertion successful.";}
}● STL unordered_map（哈希表）简介
（1）https://cplusplus.com/reference/unordered_map/unordered_map/
在 C++ 中，unordered_map 是一个基于哈希表实现的关联容器，它能够存储键值对（key-value pairs），并且允许通过键（key）来快速查找对应的值（value）。unordered_map 中的元素是无序的，这意味着它们并不按照插入的顺序或键的字母顺序进行存储。相反，unordered_map 利用哈希函数来组织数据，从而提供平均情况下接近 O(1) 的时间复杂度来进行查找、插入和删除操作。
（2）https://cplusplus.com/reference/unordered_map/unordered_map/count/
unordered_map 中的 count 函数用于计算并返回与给定键（key）相匹配的元素的数量。
由于 unordered_map 不允许有重复的键，因此对于 unordered_map 来说，count 函数的返回值只能是 0 或 1。如果给定的键存在于 unordered_map 中，则 count 返回 1；如果不存在，则返回 0。
● 本题 unordered_map 实现详见：https://blog.csdn.net/hnjzsyjyj/article/details/149003522
【算法代码：unordered_set】
若 ust 为 unordered_set，则命令 ust.insert(x).second 获取返回值的布尔部分。若为 false 表示元素已存在，若为 true 表示元素不存在。
#include <bits/stdc++.h>
using namespace std;int main() {int T;cin>>T;while(T--) {int n,x;vector<int> v;unordered_set<int> ust;cin>>n;for(int i=0; i<n; i++) {cin>>x;if(ust.insert(x).second) {v.push_back(x);}}for(int t:v) cout<<t<<" ";cout<<endl;}return 0;
}/*
in:
2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6out:
1 2 18 3 19 6 5 4
1 2 3 4 5 6
*/
【代码比较】
本题基于 unordered_map 及 unordered_set 实现的代码比较如下。
| unordered_map | unordered_set |
| #include <bits/stdc++.h> out: | #include <bits/stdc++.h> int main() { cin>>n;
for(int t:v) cout<<t<<" "; /* out: |
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/149003522
https://blog.csdn.net/hnjzsyjyj/article/details/131628676
https://blog.csdn.net/hnjzsyjyj/article/details/149002577
https://www.luogu.com.cn/problem/solution/P4305
https://blog.csdn.net/qq_17807067/article/details/127550425
