производительность - строковая операция с Java, чтобы получить наиболее повторяющийся символ

Question

Это домашнее задание проблема.

Моя строка может содержать много символов, мне нужно найти наиболее повторяющийся символ в моей строке.

Пример: str = "образец строки содержит aaaaaaaaaa # 12"; Здесь самый повторяющийся символ - это «а»

Мой код: (алгоритм)

1. Инициализированный 2D массив с размером 127 (ASCII) символов. обр [127] [2]
2. Анализ строки, увеличивая индекс массива ASCII с соответствующими значениями.

>        for(int i=0; i<str.length(); i++)
>           arr[str.charAt(1)][1] += 1;

1. Наконец, пройдемся по массиву, чтобы узнать максимальное значение arr [x] [1]

Эта проблема, для решения которой требуется O(n).

Я ищу лучшую производительность, когда размер строки очень велик.

Спасибо!

Answer 1

Я могу представить алгоритм, подобный Бойерсу-Муру, для сопоставления строк.После того, как вы определили повторяющуюся последовательность n символов, затем, чтобы проверить, длиннее ли последовательность, начинающаяся с позиции i , вам нужно проверить только позицию i + n чтобы увидеть, если это тот же символ, что и в позиции i .Если это не так, то вы начинаете проверку с позиции i + 1 ;если это так, то вы начинаете зацикливать символы между этими двумя точками, чтобы увидеть, все ли они одинаковые.Если вы все сделаете правильно, вы можете пропустить большую часть строки.В худшем случае, это все равно O (n), как и должно быть, но в лучшем случае вы можете пропустить много.

Что касается требований к месту: просто следите за самой длинной длиной пробега, исимвол (или начальная позиция). Вам не нужен двумерный массив.

Answer 2

Я не думаю, что вы можете получить лучшую эффективность TIMED, потому что нет другого способа, кроме проверки каждого символа (который я могу придумать), но вы можете добиться большей эффективности STORAGE, используя любую структуру данных на основе списка, котораяпозволяет создавать новые узлы на лету.Таким образом, вы можете просто добавлять новый элемент в список каждый раз, когда вы видите символ, которого еще нет в списке, или просто увеличивать количество элементов, уже находящихся в списке.Вам может не потребоваться 127 уникальных персонажей.

Answer 3

Вы можете сделать это за O (n) время, используя тот же подход, за исключением того, что каждый раз, когда вы обновляете значение, проверяете, превышает ли оно текущее наибольшее значение.Если это установлено как новое наибольшее значение и продолжить.Когда вы закончите, текущее наибольшее будет наибольшим значением (вы можете сохранить индекс или что-то еще, как вы можете напечатать символ в конце).

В вашем случае вы сканируете строку в O (n) но затем вы сканируете массив в конце, если вы делаете это таким образом, вы смягчаете окончательное сканирование массива на имеющемся у вас массиве значений ASCII.