今天的第二题。下面这道题呢有两种解法，一种基于哈希表，一种基于平衡树。
登录—专业IT笔试面试备考平台_牛客网
题目描述
给出N个数，要求把其中重复的去掉，只保留第一次出现的数。
例如，给出的数为1 2 18 3 3 19 2 3 6 5 4，其中2和3有重复，去除后的结果为1 2 18 3 19 6 5 4。
输入描述:
输入第一行为正整数T，表示有T组数据。 接下来每组数据包括两行，第一行为正整数N，表示有N个数。 第二行为要去重的N个正整数。
输出描述:
对于每组数据，输出一行，为去重后剩下的数字，数字之间用一个空格隔开。
示例1
输入
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
这道题使用哈希表（Hash Table）算法来实现去重操作。具体而言，我们使用了unordered_set来存储已经出现过的数，利用该数据结构的特性，可以快速判断一个数是否已经存在于集合中。通过遍历输入的数列，将每个数添加到哈希表中，并判断是否已经存在，从而实现去重操作。
在C++中，unordered_set是哈希表的实现之一，而unordered_map则是实现哈希表的关联容器。这两个容器都是C++标准库提供的，用于存储无序的键值对。在本题中，我们只需要记录数的出现情况，因此选择使用unordered_set来实现哈希表。
下面是向 unordered_set 插入和删除元素的示例代码：
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> mySet;
// 插入元素
mySet.insert(10);
mySet.insert(20);
mySet.insert(30);
// 使用范围构造函数插入元素
std::unordered_set<int> otherSet = {40, 50, 60};
mySet.insert(otherSet.begin(), otherSet.end());
// 删除元素
mySet.erase(20); // 删除值为 20 的元素
// 遍历元素
for (int num : mySet) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}本题哈希表解法代码为：
#include <iostream>
#include <unordered_set>
#include <vector>
void removeDuplicates(const std::vector<int>& nums) {
std::unordered_set<int> seen;
std::vector<int> result;
for (int i=0;i<nums.size();i++) {
if (seen.find(nums[i]) == seen.end()) {
result.push_back(nums[i]);
seen.insert(nums[i]);
}
}
for (int num : result) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
int t;
std::cin >> t;
while (t--) {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int i = 0; i < n; i++) {
std::cin >> nums[i];
}
removeDuplicates(nums);
}
return 0;
}
#include <iostream>
#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
vector<int> nums(N);
for (int i = 0; i < N; i++) {
cin >> nums[i];
}
unordered_set<int> uniqueNums;
for (int i=0;i<nums.size();i++) {
uniqueNums.insert(nums[i]);
}
for (int i=0;i<nums.size();i++) {
if (uniqueNums.count(nums[i]) > 0) {
cout << nums[i] << " ";
uniqueNums.erase(nums[i]);
}
}
cout << endl;
}
return 0;
}
平衡树和哈希表是两种不同的数据结构，在解决去重问题时可以使用它们来实现相同的功能，但它们的实现细节和性能特点有所不同。
平衡树（如红黑树、AVL树）是一种自平衡的二叉搜索树，它保持树的高度平衡，可以在O(log N)的时间复杂度内进行插入、查找和删除操作。平衡树的主要优点是可以保持元素的有序性，且插入和删除操作相对较快。因此，使用平衡树来解决去重问题时，可以保持去重后的元素有序。
哈希表是一种基于哈希函数的数据结构，通过将关键字映射到哈希表中的位置来进行查找和插入操作。哈希表的主要优点是查找和插入操作的平均时间复杂度为O(1)，即常数时间。哈希表的缺点是无法保持元素的有序性，且在存在哈希冲突时，可能需要处理冲突的情况。
对于去重问题，平衡树和哈希表的做法可以达到相同的去重效果，但它们的实现方式和性能特点有所不同。平衡树适用于需要保持元素有序性的场景，而哈希表适用于查找和插入操作频繁的场景，并且不需要保持有序性。
本题平衡树解法：
#include <iostream>
#include <set>
#include <vector>
int main() {
int T;
std::cin >> T;
while (T--) {
int N;
std::cin >> N;
std::vector<int> nums(N);
for (int i = 0; i < N; i++) {
std::cin >> nums[i];
}
std::set<int> uniqueNums;
for (int num : nums) {
if (uniqueNums.find(num) == uniqueNums.end()) {
uniqueNums.insert(num);
std::cout << num << " ";
}
}
std::cout << std::endl;
}
return 0;
}
