可以在O(n)中识别和量化字符串中的重复字符吗? [英] Can the Duplicate Characters in a string be Identified and Quantified in O(n)?

问题描述

此评论建议有一个 O(n)替代我的 O(n log n)解决此问题的方法:

This comment suggests that there is a O(n) alternative to my O(n log n) solution to this problem:

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

l = 3
o = 2

l = 3
o = 2

我的解决方案是这样做:

My solution was to do this:

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排序的限制.我认为这需要桶分类解决方案吗?我想念的还有更聪明的东西吗?

Which is obviously limited by the sorting of str. I think this would require a bucket sort solution? Is there anything more clever that I'm missing?

推荐答案

这是一种方法，即O(N)，但要为每个可能的char值维护存储.

Here's one way, which is O(N) at the expense of maintaining storage for every possible char value.

#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，因此这种便携式解决方案变得很复杂.

This portable solution is complicated by the fact that char can be signed or unsigned.

这篇关于可以在O(n)中识别和量化字符串中的重复字符吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！