Как найти наиболее часто встречающийся символ в строке
Строки – очень важная тема на собеседованиях по программированию. Перед собеседованием целесообразно попрактиковаться в некоторых задачах программирования со строками. В этой статье вы узнаете, как найти наиболее часто встречающийся символ в строке.
Примеры для понимания проблемы
Пример 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++ program to find the character
// having the highest frequency in a string
#include <iostream>
#include <string>
#define ASCII_SIZE 256
using namespace std;
char maxFrequencyChar(string str)
{
// Array to store frequency of each characters
// Initialized the frequency of each character as 0
int frequency[ASCII_SIZE] = {0};
// Finding length of the input string
int lenOfStr = str.length();
// Initialize maxFrequency variable
int maxFrequency = -1;
// Initialize maxFrequencyChar variable
char maxFrequencyChar;
// Traversing and maintaining the
// frequency of each characters
for (int i = 0; i < lenOfStr; i++)
{
frequency[str[i]]++;
if (maxFrequency < frequency[str[i]])
{
maxFrequency = frequency[str[i]];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Driver Code
int main()
{
string str1 = "Which witch is which?";
cout << "str1: " << str1 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str1) << endl;
string str2 = "He threw three free throws";
cout << "str2: " << str2 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str2) << endl;
string str3 = "Eddie edited it";
cout << "str3: " << str3 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str3) << endl;
string str4 = "Makeuseof";
cout << "str4: " << str4 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str4) << endl;
string str5 = "She sees cheese";
cout << "str5: " << str5 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str5) << endl;
}
Выход:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: eПрограмма Python для поиска символа с наибольшей частотой
Ниже приведена программа Python для поиска символа с наибольшей частотой в строке:
# Python program to find the character
# having the highest frequency in a string
ASCII_SIZE = 256
def maxFrequencyChar(str):
# Array to store frequency of each characters
# Initialized the frequency of each character as 0
frequency = [0] * ASCII_SIZE
# Initialize maxFrequency variable
maxFrequency = -1
# Initialize maxFrequencyChar variable
maxFrequencyChar = ''
# Traversing and maintaining the
# frequency of each characters
for i in str:
frequency[ord(i)] += 1
for i in str:
if maxFrequency < frequency[ord(i)]:
maxFrequency = frequency[ord(i)]
maxFrequencyChar = i
return maxFrequencyChar
# Driver Code
str1 = "Which witch is which?"
print("str1:", str1)
print("The highest frequency character is:", maxFrequencyChar(str1))
str2 = "He threw three free throws"
print("str2:", str2)
print("The highest frequency character is:", maxFrequencyChar(str2))
str3 = "Eddie edited it"
print("str3:", str3)
print("The highest frequency character is:", maxFrequencyChar(str3))
str4 = "Makeuseof"
print("str4:", str4)
print("The highest frequency character is:", maxFrequencyChar(str4))
str5 = "She sees cheese"
print("str5:", str5)
print("The highest frequency character is:", maxFrequencyChar(str5))
Выход:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: eПрограмма C для поиска символа с наибольшей частотой
Ниже приведена программа на языке C для поиска символа с наибольшей частотой в строке:
// C program to find the character
// having the highest frequency in a string
#include <iostream>
#include <cstring>
#define ASCII_SIZE 256
using namespace std;
char maxFrequencyChar(char *str)
{
// Array to store frequency of each characters
// Initialized the frequency of each character as 0
int frequency[ASCII_SIZE] = {0};
// Finding length of the input string
int lenOfStr = strlen(str);
// Initialize maxFrequency variable
int maxFrequency = 0;
// Initialize maxFrequencyChar variable
char maxFrequencyChar;
// Traversing and maintaining the
// frequency of each characters
for (int i = 0; i < lenOfStr; i++)
{
frequency[str[i]]++;
if (maxFrequency < frequency[str[i]])
{
maxFrequency = frequency[str[i]];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Driver Code
int main()
{
char str1[] = "Which witch is which?";
printf("str1: %s", str1);
printf("The highest frequency character is: %c n", maxFrequencyChar(str1));
char str2[] = "He threw three free throws";
printf("str2: %s", str2);
printf("The highest frequency character is: %c n", maxFrequencyChar(str2));
char str3[] = "Eddie edited it";
printf("str3: %s", str3);
printf("The highest frequency character is: %c n", maxFrequencyChar(str3));
char str4[] = "Makeuseof";
printf("str4: %s", str4);
printf("The highest frequency character is: %c n", maxFrequencyChar(str4));
char str5[] = "She sees cheese";
printf("str1: %s", str5);
printf("The highest frequency character is: %c n", maxFrequencyChar(str5));
}Выход:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: eПрограмма на JavaScript для поиска символа с наибольшей частотой
Ниже приведена программа на JavaScript для поиска символа с наибольшей частотой в строке:
// JavaScript program to find the character
// having the highest frequency in a string
let ASCII_SIZE = 256;
function maxFrequencyChar(str)
{
// Array to store frequency of each characters
// Initialized the frequency of each character as 0
let frequency = new Array(ASCII_SIZE);
for (let i = 0; i < ASCII_SIZE; i++)
{
frequency[i] = 0;
}
// Finding length of the input string
let lenOfStr = str.length;
for (let i = 0; i < lenOfStr; i++)
{
frequency[str[i].charCodeAt(0)] += 1;
}
// Initialize maxFrequency variable
let maxFrequency = -1;
// Initialize maxFrequencyChar variable
let maxFrequencyChar = '';
// Traversing and maintaining the
// frequency of each characters
for (let i = 0; i < lenOfStr; i++)
{
if (maxFrequency < frequency[str[i].charCodeAt(0)])
{
maxFrequency = frequency[str[i].charCodeAt(0)];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Driver Code
let str1 = "Which witch is which?";
document.write("str1: " + str1 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str1) + "<br>")
let str2 = "He threw three free throws";
document.write("str2: " + str2 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str2) + "<br>")
let str3 = "Eddie edited it";
document.write("str3: " + str3 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str3) + "<br>")
let str4 = "Makeuseof";
document.write("str4: " + str4 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str4) + "<br>")
let str5 = "She sees cheese";
document.write("str5: " + str5 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str5) + "<br>")Выход:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: eАнализируйте сложность времени и пространства
Временная сложность функции maxFrequencyChar () равна O (n) . Пространственная сложность функции maxFrequencyChar () составляет O (1) как фиксированное пространство (хэш-массив). Это не зависит от размера входной строки.
Нотация Big-O позволяет рассчитать, сколько времени потребуется для запуска вашего кода. Это одна из важнейших концепций анализа алгоритмов. Если вы программист, вы должны знать о нотации Big-O.