C++找出字符串中出现最多的字符和次数,时间复杂度小于O(n^2)

题目描述

给定一个包含n个字符的字符串S，请你编写一个复杂度小于O(n^2)的算法，找出字符串S中出现最多的字符和次数。

思路分析

本题可以采用哈希表来实现。具体的做法是，在扫描整个字符串的过程中记录下每个字符出现的次数，然后遍历所有字符，找出出现次数最多的字符即可。

遍历字符串的时间复杂度为O(n)，统计每个字符出现次数的过程为O(n)，遍历哈希表找到出现次数最多的字符也是O(n)的。因此总的时间复杂度为O(n)。

代码实现

下面给出C++的代码实现：

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main()
{
    string s = "Hello, World!";
    unordered_map<char, int> cnt_map;

    for (char c : s) {
        cnt_map[c]++;
    }

    char max_char = 0;
    int max_cnt = 0;
    for (auto p : cnt_map) {
        if (p.second > max_cnt) {
            max_cnt = p.second;
            max_char = p.first;
        }
    }

    cout << "Max char: " << max_char << endl;
    cout << "Max cnt: " << max_cnt << endl;

    return 0;
}

示例1：

给定字符串“Hello, World!”，它中出现最多的字符是字符‘l’，出现次数为3。我们可以使用上述代码来验证：

Max char: l
Max cnt: 3

示例2：

然后再给一个稍微复杂一点的字符串：“This is a test sentence to see if our code works properly or not.”，它中出现最多的字符为字符‘ ’（空格），出现次数为11。我们可以使用上述代码来验证：

Max char:
Max cnt: 11

总结

本文介绍了使用哈希表来解决C++中找出字符串中出现最多的字符和次数的问题，并给出了代码实现。