Можно ли идентифицировать и количественно определить повторяющиеся символы в строке в 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, Я думаю, что это потребует решения сортировки ведра? Есть ли что-нибудь более умное, что мне не хватает?
Решение
Вот один способ, который 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,
Другие решения
Вот что @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);
}