java — Найти часто встречающиеся буквы в журнале (n) раз?
Если задана строка типа «aaabbccc», как бы вы вывели «a», поскольку она встречается так же часто, как и «c», но встречается первой.
Я сделал это, используя время O (n), но я не могу понять, как бы вы сделали это, используя время log (n), будь то в Java или C ++.
РЕДАКТИРОВАТЬ:
Это был вопрос для интервью.
#include <iostream>
#include <string>
using std::string;
using std::cout;
using std::cin;
using std::endl;
char findFreqChar(string str) {
int count;
int maxOccur = 0;
char maxChar;
for (char i = 'A'; i < 'z'; i++) {
count = 0;
for (int j = 0; j < str.length(); j++) {
if (i == str[j])
count++;
}
if (count > maxOccur) {
maxOccur = count;
maxChar = i;
}
}
return maxChar;
}
int main() {
std::cout << "Enter String: ";
std::string str;
std::getline(std::cin, str);
cout << findFreqChar(str);
cin.get();
}
Решение
Нет способа найти наиболее часто встречающееся письмо менее чем за O(n) время, потому что вы не можете определить эту информацию без проверка каждого персонажа в строке!
Другие решения
Если вы можете гарантировать, что буквы отсортированы, как в вашем примере, то вы можете использовать бинарный поиск для определения концов каждого непрерывного диапазона букв.
Каждый бинарный поиск будет log (n); в худшем случае вам нужно сделать 25 из них, чтобы найти все границы, но «25 x постоянная x log (n)» по-прежнему O (log (n)), я полагаю.
Если вы выберете подход бинарного поиска, то есть возможность сделать это разумно — обнаружение, когда последовательные тесты в одном и том же бинарном поиске возвращают одну и ту же букву, при этом предполагается, что в качестве минимального размера диапазона, затем прерывается любой возможный диапазон, который меньше этого — но Скорее всего, вам лучше кодировать это, используя отдельные поиски. Или, возможно, лучше просто принять решение для сканирования O (n): вам действительно нужно сделать это O (log (n))?
Если вам нужно выполнить это за O (log (n)), то это говорит о том, что вам нужно разработать какой-то тип алгоритма «разделяй и властвуй». Я предполагаю (основываясь на примере, который вы нам дали), что все вхождения одного письма смежны. Поэтому мы можем сделать следующее:
1) Разбить массив пополам и рекурсивно вызвать алгоритм. Субалгоритм должен возвращать 4 значения:
— Наиболее часто встречающееся значение в массиве и его частота
— Количество смежных символов, заканчивающихся на крайнем правом символе
— Количество смежных символов, заканчивающихся на крайнем левом символе
Таким образом, рекурсивный вызов при вызове «aabbbbcc» вернется:
(б, 4, 2, 2)
2) Объедините два подмассива и верните результат для массива (теперь большего размера). Во-первых, нам нужно вычислить наиболее часто встречающийся символ в объединенном массиве. Это легко вычисляется как самая длинная последовательность справа, самая длинная последовательность слева или последовательность, которая охватывает точку разделения (именно поэтому нам потребовались последние 2 значения из рекурсивного вызова). Это все может быть сделано в постоянное время. Мы также возвращаем соответствующие значения из двух рекурсивных вызовов для длины непрерывных символов, заканчивающихся на крайнем правом и левом символах.
Эта рекурсия заканчивается тем, что T (n) = T (n / 2) + O (1) или O (lg n)
Существует довольно много граничных случаев, и вам необходимо выяснить, как обращаться с ними, когда рекурсия «заканчивается», но этого должно быть достаточно для написания кода.