算法分析

哈希表

• 1、通过指针扫描的方式将每个单词存入到哈希表中，并注意切换成小写
• 2、枚举哈希表找出最常用词word以及其出现次数res（若次数相同，找字典序最小）

时间复杂度 $O(n)$

参考文献

pat

C++ 代码

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<string, int> map;

bool check(char c)
{
    if(c >= 'A' && c <= 'Z') return true;
    if(c >= 'a' && c <= 'z') return true;
    if(c >= '0' && c <= '9') return true;
    return false;
}
char get(char c)
{
    if(c >= 'A' && c <= 'Z') return c + 32;
    return c;
}
int main()
{
    string s;
    getline(cin, s);

    for(int i = 0; i < s.size(); i ++ )
    {
        if(check(s[i]))
        {
            string word;
            int j = i;
            while(j < s.size() && check(s[j])) word += get(s[j ++]);

            map[word] ++;

            i = j;
        }
    }
    string word;
    int res = 0;
    for(auto item : map)
    {
        if(item.second > res || (item.second == res && item.first < word))
        {
            word = item.first;
            res = item.second;
        }
    }
    cout << word << " " << res << endl;

    return 0;
}