题目分析

1. 题目给出了一个字符串
2. 我们要返回这个字符串中出现的字符种类个数

方法一：枚举

• 实现思路

  • 我们根据ASCII的表示范围开辟128大小的空间

  • 对每个出现的字符在我们的aux空间中标记其已出现，值设置为1

  • 最终统计所有出现种类之和，返回最终结果

#include <iostream>

using namespace std;

int main() {
    string s;
    cin >> s;
    int aux[128] = {0};						// 根据ASCII表示范围来开辟一个空间
    for(char c : s) {						// 遍历并枚举标记种类出现
        aux[c] = 1;
    }
    int kind = 0;
    for(int i = 0; i < 128; i++) {			// 统计所有出现的字符种类数目
        kind += aux[i];
    }
    cout << kind;
    return 0;
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，对字符串进行一遍遍历的时间开销
• 空间复杂度：$O(1)O(1)$，采用常数级别的空间开销

方法二：哈希表

• 实现思路
  • 使用哈希表来存储
  • 使用unordered_map结构给字符构造一个哈希表
  • 遍历字符串，如果遇到一个字符后就将其放入哈希表中
  • 最后查看哈希表的容量大小即可

#include<iostream>
#include<unordered_map>
using namespace std;

int main() {
    string str; cin >> str;
    unordered_map<char, int> m;	  // 哈希表
    for(char c : str) m[c] = 1;		// 录入哈希表
    cout << m.size() << endl;		// 返回哈希表的空间大小
    return 0;
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历字符串的时间开销
• 空间复杂度：$O(1)O(1)$，由于ASCII表示的字符种类有限，因此哈希表的空间大小也是有限的常量级别的