牛客4590题解：高效去重字符集合的C++实现（哈希表+字符串遍历）

一、题目解读

牛客4590题要求处理一个字符串，输出其中所有不同的字符组成的集合（即去除重复字符后的字符集合）。题目涉及多组输入，需要依次处理每个字符串并输出其唯一字符集。核心在于快速识别并存储不同字符，避免重复输出。

二、解题思路

采用哈希表实现高效去重。思路分为两部分：

1. 字符唯一性记录：利用无序集合（unordered_set<char> seen）存储已出现的字符，通过find()方法快速判断字符是否首次出现。

2. 结果构建与输出：遍历字符串时，若字符未存在于seen中，则将其插入集合并添加到结果字符串（result），最终输出结果。

该思路时间复杂度为O(N)，空间复杂度为O(N)，适用于处理大规模字符串输入。

三、解题步骤

1. 定义函数printCharacterSet()，接收字符串参数s。

2. 初始化哈希表seen和结果字符串result。

3. 遍历字符串s中的每个字符：

○ 若字符c未在seen中（通过seen.find(c) == seen.end()判断），则执行以下操作：

■ 将c插入seen标记为已出现。

■ 将c追加到result末尾。

4. 输出result作为去重后的字符集合。

5. 主函数中通过while(cin >> input)循环处理多组输入，调用函数并输出结果。

四、代码与注释

#include <iostream>  
#include <string>  
#include <unordered_set>  
using namespace std;  

// 函数：获取并输出字符串的字符集合  
void printCharacterSet(const string& s) {  
    unordered_set<char> seen;  // 用于记录已经出现过的字符  
    string result;             // 存储结果字符集合  

    // 遍历字符串中的每个字符  
    for (char c : s) {  
        // 如果字符还未出现过  
        if (seen.find(c) == seen.end()) {  
            seen.insert(c);     // 标记为已出现  
            result += c;        // 添加到结果中  
        }  
    }  

    cout << result << endl;  // 输出结果  
}  

int main() {  
    string input;  
    // 处理多组输入  
    while (cin >> input) {  
        printCharacterSet(input);  
    }  
    return 0;  
}

五、总结

本解法通过哈希表实现了字符串字符集合的快速去重，核心优势在于：

● 无序集合的常数时间查找：find()和insert()操作平均时间复杂度为O(1)，大幅提升效率。

● 简洁的遍历逻辑：单次遍历即可完成去重与结果构建，无需额外排序或复杂比较。

● 多组输入处理：利用while(cin >> input)循环，灵活应对题目中的多案例需求。

该思路适用于需要高效去重字符的场景，是处理字符串集合问题的经典方法。