Как да намерим най-често срещания характер в низ

Струните са много важна тема в интервютата за програмиране. Разумно е да практикувате някои проблеми с програмирането, фокусирани върху струните, преди вашите интервюта. В тази статия ще научите как да намерите най-често срещания знак в низ.

Примери за разбиране на проблема

Пример 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 ++ програма за намиране на символа
// с най-висока честота в низ
#include 
#include 
#define ASCII_SIZE 256
използване на пространство от имена std;
char maxFrequencyChar (низ str)
{
// Масив за съхраняване на честотата на всеки знак
// Инициализира честотата на всеки знак като 0
int честота [ASCII_SIZE] = {0};
// Намиране на дължина на входния низ
int lenOfStr = str.length ();
// Инициализиране на променлива maxFrequency
int maxFrequency = -1;
// Инициализира променливата maxFrequencyChar
char maxFrequencyChar;
// Преминаване и поддържане на
// честота на всеки знак
за (int i = 0; i {
честота [str [i]] ++;
if (maxFrequency {
maxFrequency = честота [str [i]];
maxFrequencyChar = str [i];
}
}
връщане maxFrequencyChar;
}
// Код на водача
int main ()
{
низ str1 = "Коя вещица коя е?";
cout << "str1:" << str1 << endl;
cout << "Символът с най-висока честота е:" << maxFrequencyChar (str1) << endl;
низ str2 = "Той хвърли три свободни хвърляния";
cout << "str2:" << str2 << endl;
cout << "Символът с най-висока честота е:" << maxFrequencyChar (str2) << endl;
низ str3 = "Еди го редактира";
cout << "str3:" << str3 << endl;
cout << "Символът с най-висока честота е:" << maxFrequencyChar (str3) << endl;
низ str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Символът с най-висока честота е:" << maxFrequencyChar (str4) << endl;
низ 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 = i
върнете maxFrequencyChar
# Код на водача
str1 = "Коя вещица коя е?"
печат ("str1:", str1)
print ("Символът с най-висока честота е:", maxFrequencyChar (str1))
str2 = "Той хвърли три свободни хвърляния"
печат ("str2:", str2)
print ("Символът с най-висока честота е:", maxFrequencyChar (str2))
str3 = "Еди го редактира"
печат ("str3:", str3)
print ("Символът с най-висока честота е:", maxFrequencyChar (str3))
str4 = "Използване на"
печат ("str4:", str4)
print ("Символът с най-висока честота е:", maxFrequencyChar (str4))
str5 = "Тя вижда сирене"
печат ("str5:", str5)
print ("Символът с най-висока честота е:", maxFrequencyChar (str5))

Изход:

str1: Коя вещица е коя?
Символът с най-висока честота е: h
str2: Той хвърли три свободни хвърляния
Символът с най-висока честота е: e
str3: Еди го редактира
Символът с най-висока честота е: d
str4: Makeuseof
Символът с най-висока честота е: e
str5: Тя вижда сирене
Символът с най-висока честота е: e

Програма C за намиране на персонажа с най-висока честота

По-долу е програмата C за намиране на знака с най-висока честота в низ:

Свързани: Как да намерим гласни, съгласни, цифри и специални символи в низ

// C програма за намиране на героя
// с най-висока честота в низ
#include 
#include 
#define ASCII_SIZE 256
използване на пространство от имена std;
char maxFrequencyChar (char * str)
{
// Масив за съхраняване на честотата на всеки знак
// Инициализира честотата на всеки знак като 0
int честота [ASCII_SIZE] = {0};
// Намиране на дължина на входния низ
int lenOfStr = strlen (str);
// Инициализиране на променлива maxFrequency
int maxFrequency = 0;
// Инициализира променливата maxFrequencyChar
char maxFrequencyChar;
// Преминаване и поддържане на
// честота на всеки знак
за (int i = 0; i {
честота [str [i]] ++;
if (maxFrequency {
maxFrequency = честота [str [i]];
maxFrequencyChar = str [i];
}
}
връщане 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 {
честота [i] = 0;
}
// Намиране на дължина на входния низ
нека lenOfStr = str.length;
за (нека i = 0; i {
честота [str [i] .charCodeAt (0)] + = 1;
}
// Инициализиране на променлива maxFrequency
нека maxFrequency = -1;
// Инициализира променливата maxFrequencyChar
нека maxFrequencyChar = '';
// Преминаване и поддържане на
// честота на всеки знак
за (нека i = 0; i {
if (maxFrequency {
maxFrequency = честота [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
връщане maxFrequencyChar;
}
// Код на водача
нека str1 = "Коя вещица коя е?";
document.write ("str1:" + str1 + "
");
document.write ("Символът с най-висока честота е:" + maxFrequencyChar (str1) + "
")
let str2 = "Той хвърли три свободни хвърляния";
document.write ("str2:" + str2 + "
");
document.write ("Символът с най-висока честота е:" + maxFrequencyChar (str2) + "
")
нека str3 = "Еди го редактира";
document.write ("str3:" + str3 + "
");
document.write ("Символът с най-висока честота е:" + maxFrequencyChar (str3) + "
")
нека 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 () функцията е O (1) като фиксирано пространство (Hash масив). Това не зависи от размера на входния низ.

Нотацията Big-O ви дава начин да изчислите колко време ще отнеме стартирането на вашия код. Това е една от най-важните концепции за анализ на алгоритми. Ако сте програмист, трябва да знаете за Big-O Notation.

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

Yuvraj е студент по компютърни науки в Университета на Делхи, Индия. Той е запален по Full Stack Web Development. Когато не пише, той изследва дълбочината на различните технологии.

Още от Юврадж Чандра