【題目來源】
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
?
?
