Можно ли идентифицировать и количественно идентифицировать повторяющиеся символы в строке в O (n)?

Этот комментарий говорит о том, что существует альтернатива 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. Я думаю, для этого потребуется решение для сортировки в виде ковша? Есть ли что-нибудь более умное, чего я не хватает?

Ответы

Ответ 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.

Ответ 2

Вот что @bathsheba упоминается и с улучшениями @Holt:

#include <string>
#include <climits>
#include <iostream>

void show_dup(const std::string& str) {
    const int sz = CHAR_MAX - CHAR_MIN + 1;
    int all_chars[sz] = { 0 };
    // O(N), N - the length of input string
    for(char c : str) {
        int idx = (int)c;
        all_chars[idx]++;
    }
    // O(sz) - constant. For ASCII char it will be 256
    for(int i = 0; i < sz; i++) {
        if (all_chars[i] > 1) {
            std::cout << (char)i << " = " << all_chars[i] << std::endl;
        }
    }
}

int main()
{
  std::string str("helloWorld");

  show_dup(str);
}