c++ - 能否在 O(n) 中识别和量化字符串中的重复字符？

Question

This comment建议有一个 O(n) 替代方案来替代我的 O(n log n) 解决这个问题:

给定 string str("helloWorld") 预期的输出是:

l = 3
o = 2

我的解决方案是这样做:

sort(begin(str), end(str));

for(auto start = adjacent_find(cbegin(str), cend(str)), finish = upper_bound(start, cend(str), *start); start != cend(str); start = adjacent_find(finish, cend(str)), finish = upper_bound(start, cend(str), *start)) {
   cout << *start << " = " << distance(start, finish) << endl;
}

这显然受限于str的排序。我认为这需要桶排序解决方案？我还缺少什么更聪明的东西吗？

Answer 1

这是一种方法，它是 O(N) 的，代价是为每个可能的 char 值维护存储空间。

#include <string>
#include <limits.h> // for CHAR_MIN and CHAR_MAX. Old habits die hard.

int main()
{
    std::string s("Hello World");        
    int storage[CHAR_MAX - CHAR_MIN + 1] = {};
    for (auto c : s){
        ++storage[c - CHAR_MIN];
    }

    for (int c = CHAR_MIN; c <= CHAR_MAX; ++c){
        if (storage[c - CHAR_MIN] > 1){
            std::cout << (char)c << " " << storage[c - CHAR_MIN] << "\n";
        }
    }    
}

由于char 可以是signed 或unsigned，所以这个可移植的解决方案很复杂。