牛客——不重复数字（哈希表、平衡树）

今天的第二题。

登录—专业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;
}