Самый частый персонаж в диапазоне

Сделайте одну итерацию по массиву и для каждой позиции запомните, сколько вхождений каждого символа существует до этой позиции. Так что-то вроде этого:

"abcdabc"

для индекса 0:

count['a'] = 1
count['b'] = 0
etc...

для индекса 1:

....
count['a'] = 1
count['b'] = 1
count['c'] = 0
etc...

для индекса 2:

....
count['a'] = 1
count['b'] = 1
count['c'] = 1
....

И так далее. Для индекса 6:

....
count['a'] = 2
count['b'] = 2
count['c'] = 2
count['d'] = 1
... all others are 0

После того, как вы вычислите этот массив, вы можете получить количество вхождений данной буквы в интервале (i, j) в постоянное время — просто вычислите count[j] - count[i-1] (осторожно здесь для i = 0!).

Таким образом, для каждого запроса вам придется выполнять итерации по всем буквам, а не по всем символам в интервале, и, таким образом, вместо итерации по 10 ^ 6 символам вы будете передавать только максимум 128 (при условии, что у вас есть только символы ASCII).

Недостаток — вам нужно больше памяти, в зависимости от размера алфавита, который вы используете.

Если вы хотите получать эффективные результаты по интервалам, вы можете построить интегральный вектор распределения для каждого индекса вашей последовательности. Затем, вычитая интегральные распределения в j + 1 и i, вы можете получить распределение на интервале из s [i], s [i + 1], …, s [j].

Некоторый псевдокод в Python следует. Я предполагаю, что ваши персонажи являются символами, следовательно, 256 записей распределения.

def buildIntegralDistributions(s):
IDs=[]        # integral distribution
D=[0]*256
IDs.append(D[:])
for x in s:
D[ord(x)]+=1
IDs.append(D[:])
return IDs

def getIntervalDistribution(IDs, i,j):
D=[0]*256
for k in range(256):
D[k]=IDs[j][k]-IDs[i][k]
return D

s='abababbbb'
IDs=buildIntegralDistributions(s)
Dij=getIntervalDistribution(IDs, 2,4)

>>> s[2:4]
'ab'
>>> Dij[ord('a')]  # how many 'a'-s in s[2:4]?
1
>>> Dij[ord('b')]  # how many 'b'-s in s[2:4]?
1

Вам необходимо указать свои алгоритмические требования с точки зрения сложности пространства и времени.

Если вы настаиваете на O(1) сложность пространства, просто сортировка (например, с использованием лексикографического упорядочения битов, если нет доступного оператора естественного сравнения) и подсчет количества вхождений самого высокого элемента даст вам O(N log N) сложность времени.

Если вы настаиваете на O(N) сложность времени, используйте решение @Luchian Grigore, которое также принимает O(N) космическая сложность (ну, O(K) за Kбуква алфавита).

string="something"arrCount[string.length()];

после каждого доступа к строке вызывать freq ()

freq(char accessedChar){
arrCount[string.indexOf(x)]+=1
}

чтобы получить наиболее частый символ, позвоните string.charAt(arrCount.max())

при условии, что строка является постоянной и отличается i а также j будет передан в запрос запросов.

Если вы хотите минимизировать время обработки, вы можете сделать

struct occurences{
char c;
std::list<int> positions;
};

и держать std::list<occurences> для каждого персонажа. для быстрого поиска вы можете сохранить positions приказал.

и если вы хотите минимизировать объем памяти, вы можете просто сохранить возрастающее целое число и выполнить цикл i .. j

Как было предложено, наиболее эффективным по времени алгоритмом является сохранение частот каждого символа в массиве. Однако обратите внимание, что если вы просто индексируете массив с помощью символов, вы можете вызвать неопределенное поведение. А именно, если вы обрабатываете текст, содержащий кодовые точки за пределами диапазона 0x00-0x7F, например текст, закодированный с помощью UTF-8, в лучшем случае вы можете столкнуться с нарушением сегментации, а в худшем случае с повреждением данных в стеке:

char frequncies [256] = {};
frequencies ['á'] = 9; // Oops. If our implementation represents char using a
// signed eight-bit integer, we just referenced memory
// outside of our array bounds!

Решение, которое правильно учитывает это, будет выглядеть примерно так:

template <typename charT>
charT most_frequent (const basic_string <charT>& str)
{
constexpr auto charT_max = numeric_limits <charT>::max ();
constexpr auto charT_min = numeric_limits <charT>::lowest ();
size_t frequencies [charT_max - charT_min + 1] = {};

for (auto c : str)
++frequencies [c - charT_min];

charT most_frequent;
size_t count = 0;
for (charT c = charT_min; c < charT_max; ++c)
if (frequencies [c - charT_min] > count)
{
most_frequent = c;
count = frequencies [c - charT_min];
}

// We have to check charT_max outside of the loop,
// as otherwise it will probably never terminate
if (frequencies [charT_max - charT_min] > count)
return charT_max;

return most_frequent;
}

Если вы хотите перебирать одну и ту же строку несколько раз, измените приведенный выше алгоритм (как construct_array) использовать std::array <size_t, numeric_limits <charT>::max () - numeric_limits <charT>::lowest () + 1>, Затем верните этот массив вместо символа max после первого цикла for и пропустите часть алгоритма, которая находит наиболее часто встречающийся символ. Построить std::map <std::string, std::array <...>> в вашем коде верхнего уровня и сохранить возвращенный массив в этом. Затем переместите код для поиска наиболее часто встречающегося символа в этот код верхнего уровня и используйте массив кэшированных счетчиков:

char most_frequent (string s)
{
static map <string, array <...>> cache;

if (cache.count (s) == 0)
map [s] = construct_array (s);
// find the most frequent character, as above, replacing `frequencies`
// with map [s], then return it
}

Теперь это работает только для целых строк. Если вы хотите обрабатывать относительно небольшие подстроки несколько раз, вам следует использовать первую версию. В противном случае я бы сказал, что вам лучше всего делать что-то вроде второго решения, но разбивать строку на управляемые куски; таким образом, вы можете извлечь большую часть информации из вашего кэша, только пересчитав частоты в порциях, в которых находятся ваши итераторы.

быстрый будет использовать unordered_map или похожие:

pair<char, int> fast(const string& s) {
unordered_map<char, int> result;

for(const auto i : s) ++result[i];
return *max_element(cbegin(result), cend(result), [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; });
}

самый светлый, в отношении памяти, потребуется непостоянный ввод, который может быть отсортирован так, что find_first_not_of или аналогичные могут быть использованы:

pair<char, int> light(string& s) {
pair<char, int> result;
int start = 0;

sort(begin(s), end(s));
for(auto finish = s.find_first_not_of(s.front()); finish != string::npos; start = finish, finish = s.find_first_not_of(s[start], start)) if(const int second = finish - start; second > result.second) result = make_pair(s[start], second);
if(const int second = size(s) - start; second > result.second) result = make_pair(s[start], second);
return result;
}

Следует отметить, что обе эти функции имеют условие непустой строки. Также, если в строке есть связь для большинства символов, обе функции будут возвращать символ, который в первую очередь лексографически имеет наибольшее количество символов.

Живой пример