Как найти наиболее часто встречающийся символ в строке

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

Примеры для понимания проблемы

Пример 1: Пусть данная строка будет "Makeuseof". Символ 'e' встречается в данной строке 2 раза, а все остальные символы встречаются только один раз. Таким образом, символ 'e' имеет самую высокую частоту в данной строке.

Пример 2: Пусть данная строка будет «Она видит сыр». Символ 'e' встречается в данной строке 6 раз, а все остальные символы встречаются менее 6 раз. Таким образом, символ 'e' имеет самую высокую частоту в данной строке.

Подход к поиску наиболее часто встречающегося символа в строке

Техника хеширования - самый эффективный способ найти символ, имеющий самую высокую частоту в строке. В этом методе выполняется обход строки, и каждый символ строки хешируется в массив символов ASCII.

Пусть входная строка будет "Makeuseof", каждый символ этой строки хешируется следующим образом:

частота ['M'] = 1

частота ['a] = 1

частота ['k'] = 1

частота ['e'] = 2

частота ['u'] = 1

частота ['s'] = 1

частота ['o'] = 1

частота ['f'] = 1

Возвращается индекс максимального значения в массиве частот. Здесь 2 является наивысшим значением, поэтому возвращается 'e'.

Программа C ++ для поиска символа с наибольшей частотой

Ниже приведена программа на C ++ для поиска символа с наибольшей частотой в строке:

Связанный: Как подсчитать количество вхождений данного символа в строку

// Программа на C ++ для поиска символа
// имеющий самую высокую частоту в строке
#включать 
#включать 
#define ASCII_SIZE 256
используя пространство имен std;
char maxFrequencyChar (строка str)
{
// Массив для хранения частоты каждого символа
// Инициализировал частоту каждого символа как 0
int частота [ASCII_SIZE] = {0};
// Находим длину входной строки
int lenOfStr = длина строки ();
// Инициализируем переменную maxFrequency
int maxFrequency = -1;
// Инициализируем переменную maxFrequencyChar
char maxFrequencyChar;
// Обход и поддержание
// частота каждого символа
для (int i = 0; я {
частота [str [i]] ++;
если (maxFrequency {
maxFrequency = частота [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Код драйвера
int main ()
{
string str1 = "Какая ведьма какая?";
cout << "str1:" << str1 << endl;
cout << "Самый частый символ:" << maxFrequencyChar (str1) << endl;
string str2 = "Он выполнил три штрафных броска";
cout << "str2:" << str2 << endl;
cout << "Самый частый символ:" << maxFrequencyChar (str2) << endl;
string str3 = "Эдди редактировал это";
cout << "str3:" << str3 << endl;
cout << "Самый частый символ:" << maxFrequencyChar (str3) << endl;
строка str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Самый частый символ:" << maxFrequencyChar (str4) << endl;
string str5 = "Она видит сыр";
cout << "str5:" << str5 << endl;
cout << "Самый частый символ:" << maxFrequencyChar (str5) << endl;
}

Выход:

str1: Какая ведьма какая?
Самый частый символ: h
str2: Он бросил три штрафных броска
Самый частый символ: e
str3: Эдди редактировал это
Самый частый символ: d
str4: Makeuseof
Самый частый символ: e
str5: Она видит сыр
Самый частый символ: e

Программа Python для поиска символа с наибольшей частотой

Ниже приведена программа Python для поиска символа с наибольшей частотой в строке:

Связанный: Как перевернуть строку в C ++, Python и JavaScript

# Программа на Python для поиска персонажа
# самая высокая частота в строке
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Массив для хранения частоты каждого символа
# Инициализировал частоту каждого символа как 0
частота = [0] * ASCII_SIZE
# Инициализировать переменную maxFrequency
maxFrequency = -1
# Инициализировать переменную maxFrequencyChar
maxFrequencyChar = ''
# Обход и обслуживание
# частота каждого символа
для i в str:
частота [ord (i)] + = 1
для i в str:
если maxFrequency maxFrequency = частота [ord (i)]
maxFrequencyChar = я
вернуть maxFrequencyChar
# Код драйвера
str1 = "Какая ведьма какая?"
print ("str1:", str1)
print ("Самый частый символ:", maxFrequencyChar (str1))
str2 = "Он бросил три штрафных броска"
print ("str2:", str2)
print ("Самый частый символ:", maxFrequencyChar (str2))
str3 = "Эдди редактировал это"
print ("str3:", str3)
print ("Самый частый символ:", maxFrequencyChar (str3))
str4 = "Makeuseof"
print ("str4:", str4)
print ("Самый частый символ:", maxFrequencyChar (str4))
str5 = "Она видит сыр"
print ("str5:", str5)
print ("Самый частый символ:", maxFrequencyChar (str5))

Выход:

str1: Какая ведьма какая?
Самый частый символ: h
str2: Он бросил три штрафных броска
Самый частый символ: e
str3: Эдди редактировал это
Самый частый символ: d
str4: Makeuseof
Самый частый символ: e
str5: Она видит сыр
Самый частый символ: e

Программа C для поиска символа с наибольшей частотой

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

Связанный: Как найти в строке гласные, согласные, цифры и специальные символы

// Программа на C для поиска символа
// имеющий самую высокую частоту в строке
#включать 
#включать 
#define ASCII_SIZE 256
используя пространство имен std;
char maxFrequencyChar (char * str)
{
// Массив для хранения частоты каждого символа
// Инициализировал частоту каждого символа как 0
int частота [ASCII_SIZE] = {0};
// Находим длину входной строки
int lenOfStr = strlen (стр);
// Инициализируем переменную maxFrequency
int maxFrequency = 0;
// Инициализируем переменную maxFrequencyChar
char maxFrequencyChar;
// Обход и поддержание
// частота каждого символа
для (int i = 0; я {
частота [str [i]] ++;
если (maxFrequency {
maxFrequency = частота [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Код драйвера
int main ()
{
char str1 [] = "Какая ведьма какая?";
printf ("str1:% s", str1);
printf ("Самый частый символ:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Он бросил три штрафных броска";
printf ("str2:% s", str2);
printf ("Самый частый символ:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Эдди редактировал это";
printf ("str3:% s", str3);
printf ("Самый частый символ:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Самый частый символ:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Она видит сыр";
printf ("str1:% s", str5);
printf ("Самый частый символ:% c \ ⁠n", maxFrequencyChar (str5));
}

Выход:

str1: Какая ведьма какая?
Самый частый символ: h
str2: Он бросил три штрафных броска
Самый частый символ: e
str3: Эдди редактировал это
Самый частый символ: d
str4: Makeuseof
Самый частый символ: e
str5: Она видит сыр
Самый частый символ: e

Программа на JavaScript для поиска символа с наибольшей частотой

Ниже приведена программа на JavaScript для поиска символа с наибольшей частотой в строке:

// Программа на JavaScript для поиска символа
// имеющий самую высокую частоту в строке
пусть ASCII_SIZE = 256;
функция maxFrequencyChar (str)
{
// Массив для хранения частоты каждого символа
// Инициализировал частоту каждого символа как 0
пусть частота = новый массив (ASCII_SIZE);
для (пусть i = 0; я {
частота [i] = 0;
}
// Находим длину входной строки
пусть lenOfStr = str.length;
для (пусть i = 0; я {
частота [str [i] .charCodeAt (0)] + = 1;
}
// Инициализируем переменную maxFrequency
пусть maxFrequency = -1;
// Инициализируем переменную maxFrequencyChar
let maxFrequencyChar = '';
// Обход и поддержание
// частота каждого символа
для (пусть i = 0; я {
если (maxFrequency {
maxFrequency = частота [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Код драйвера
let str1 = "Какая ведьма какая?";
document.write ("str1:" + str1 + "
");
document.write ("Самый частый символ:" + maxFrequencyChar (str1) + "
")
let str2 = "Он выполнил три штрафных броска";
document.write ("str2:" + str2 + "
");
document.write ("Самый частый символ:" + maxFrequencyChar (str2) + "
")
let str3 = "Эдди редактировал это";
document.write ("str3:" + str3 + "
");
document.write ("Самый частый символ:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Самый частый символ:" + maxFrequencyChar (str4) + "
")
let str5 = "Она видит сыр";
document.write ("str5:" + str5 + "
");
document.write ("Самый частый символ:" + maxFrequencyChar (str5) + "
")

Выход:

str1: Какая ведьма какая?
Самый частый символ: h
str2: Он бросил три штрафных броска
Самый частый символ: e
str3: Эдди редактировал это
Самый частый символ: d
str4: Makeuseof
Самый частый символ: e
str5: Она видит сыр
Самый частый символ: e

Анализируйте сложность времени и пространства

Временная сложность maxFrequencyChar () функция На). Космическая сложность maxFrequencyChar () функция О (1) как фиксированное пространство (массив хешей). Это не зависит от размера входной строки.

Нотация Big-O позволяет рассчитать, сколько времени потребуется для запуска вашего кода. Это одна из важнейших концепций анализа алгоритмов. Если вы программист, вы должны знать о нотации Big-O.

Юврадж Чандра (Опубликовано 30 статей)

Юврадж - студент бакалавриата по информатике в Университете Дели, Индия. Он увлечен веб-разработкой Full Stack. Когда он не пишет, он исследует глубину различных технологий.

Ещё от Yuvraj Chandra