Sådan finder du den hyppigst forekommende karakter i en streng

Strenge er et meget vigtigt emne i programmering af interviews. Det er klogt at øve nogle programmeringsproblemer med fokus på strenge før dine interviews. I denne artikel lærer du, hvordan du finder det hyppigst forekommende tegn i en streng.

Eksempler til forståelse af problemet

Eksempel 1: Lad den givne streng være "Makeuseof". Tegnet 'e' forekommer 2 gange i den givne streng, og alle de andre tegn forekommer kun én gang. Således har tegnet 'e' den højeste frekvens i den givne streng.

Eksempel 2: Lad den givne streng være "Hun ser ost". Tegnet 'e' forekommer 6 gange i den givne streng, og alle de andre tegn forekommer mindre end 6 gange. Således har tegnet 'e' den højeste frekvens i den givne streng.

Tilgang til at finde den hyppigst forekommende karakter i en streng

Hash-teknikken er den mest effektive måde at finde det tegn, der har den højeste frekvens i en streng. I denne teknik krydses strengen, og hvert tegn i strengen hasheres i en matrix med ASCII-tegn.

Lad inputstrengen være "Makeuseof", hvert tegn i denne streng hashes som følger:

frekvens ['M'] = 1

frekvens ['a] = 1

frekvens ['k'] = 1

frekvens ['e'] = 2

frekvens ['u'] = 1

frekvens ['s'] = 1

frekvens ['o'] = 1

frekvens ['f'] = 1

Indekset for den maksimale værdi i frekvensarrayet returneres. Her 2 er den højeste værdi, derfor returneres 'e'.

C ++ - program til at finde karakteren med den højeste frekvens

Nedenfor er C ++ - programmet til at finde tegnet med den højeste frekvens i en streng:

Relaterede: Sådan tælles forekomsterne af en given karakter i en streng

// C ++ - program for at finde tegnet
// har den højeste frekvens i en streng
#omfatte 
#omfatte 
#definer ASCII_SIZE 256
ved hjælp af namespace std;
char maxFrequencyChar (streng str)
{
// Array for at gemme hyppigheden af ​​hvert tegn
// Initialiserede hyppigheden af ​​hvert tegn som 0
int frekvens [ASCII_SIZE] = {0};
// Find længde af inputstrengen
int lenOfStr = str.length ();
// Initialiser maxFrequency-variablen
int maxFrequency = -1;
// Initialiser variablen maxFrequencyChar
char maxFrequencyChar;
// Traversering og vedligeholdelse af
// hyppigheden af ​​hvert tegn
for (int i = 0; i {
frekvens [str [i]] ++;
hvis (maxFrequency {
maxFrequency = frekvens [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Førerkode
int main ()
{
string str1 = "Hvilken heks er hvilken?";
cout << "str1:" << str1 << endl;
cout << "Den højeste frekvens er:" << maxFrequencyChar (str1) << endl;
string str2 = "Han kastede tre straffekast";
cout << "str2:" << str2 << endl;
cout << "Den højeste frekvens er:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie redigerede det";
cout << "str3:" << str3 << endl;
cout << "Den højeste frekvens er:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Den højeste frekvens er:" << maxFrequencyChar (str4) << endl;
string str5 = "Hun ser ost";
cout << "str5:" << str5 << endl;
cout << "Den højeste frekvens er:" << maxFrequencyChar (str5) << endl;
}

Produktion:

str1: Hvilken heks er hvilken?
Den højeste frekvens er: h
str2: Han kastede tre straffekast
Den højeste frekvens er: e
str3: Eddie redigerede det
Den højeste frekvens er: d
str4: Makeuseof
Den højeste frekvens er: e
str5: Hun ser ost
Den højeste frekvens er: e

Python-program til at finde karakteren med den højeste frekvens

Nedenfor er Python-programmet for at finde tegnet med den højeste frekvens i en streng:

Relaterede: Sådan vendes en streng i C ++, Python og JavaScript

# Python-program for at finde tegnet
# har den højeste frekvens i en streng
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Array for at gemme hyppigheden af ​​hvert tegn
# Initialiserede hyppigheden af ​​hvert tegn som 0
frekvens = [0] * ASCII_SIZE
# Initialiser variablen maxFrequency
maxFrequency = -1
# Initialiser maxFrequencyChar-variablen
maxFrequencyChar = ''
# Traversering og vedligeholdelse af
# hyppighed for hvert tegn
for jeg i str:
frekvens [ord (i)] + = 1
for jeg i str:
hvis maxFrequency maxFrequency = frekvens [ord (i)]
maxFrequencyChar = i
return maxFrequencyChar
# Førerkode
str1 = "Hvilken heks er hvilken?"
print ("str1:", str1)
print ("Det højeste frekvenstegn er:", maxFrequencyChar (str1))
str2 = "Han kastede tre straffekast"
print ("str2:", str2)
print ("Det højeste frekvenstegn er:", maxFrequencyChar (str2))
str3 = "Eddie redigerede det"
print ("str3:", str3)
print ("Den højeste frekvens er:", maxFrequencyChar (str3))
str4 = "Makeuseof"
print ("str4:", str4)
print ("Den højeste frekvens er:", maxFrequencyChar (str4))
str5 = "Hun ser ost"
print ("str5:", str5)
print ("Den højeste frekvens er:", maxFrequencyChar (str5))

Produktion:

str1: Hvilken heks er hvilken?
Den højeste frekvens er: h
str2: Han kastede tre straffekast
Den højeste frekvens er: e
str3: Eddie redigerede det
Den højeste frekvens er: d
str4: Makeuseof
Den højeste frekvens er: e
str5: Hun ser ost
Den højeste frekvens er: e

C Program til at finde karakteren med den højeste frekvens

Nedenfor er C-programmet til at finde tegnet med den højeste frekvens i en streng:

Relaterede: Sådan finder du vokaler, konsonanter, cifre og specialtegn i en streng

// C-program for at finde tegnet
// har den højeste frekvens i en streng
#omfatte 
#omfatte 
#definer ASCII_SIZE 256
ved hjælp af namespace std;
char maxFrequencyChar (char * str)
{
// Array for at gemme hyppigheden af ​​hvert tegn
// Initialiserede hyppigheden af ​​hvert tegn som 0
int frekvens [ASCII_SIZE] = {0};
// Find længde af inputstrengen
int lenOfStr = strlen (str);
// Initialiser maxFrequency-variablen
int maxFrequency = 0;
// Initialiser variablen maxFrequencyChar
char maxFrequencyChar;
// Traversering og vedligeholdelse af
// hyppigheden af ​​hvert tegn
for (int i = 0; i {
frekvens [str [i]] ++;
hvis (maxFrequency {
maxFrequency = frekvens [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Førerkode
int main ()
{
char str1 [] = "Hvilken heks er hvilken?";
printf ("str1:% s", str1);
printf ("Det højeste frekvenstegn er:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Han kastede tre straffekast";
printf ("str2:% s", str2);
printf ("Det højeste frekvenstegn er:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie redigerede det";
printf ("str3:% s", str3);
printf ("Det højeste frekvenstegn er:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Det højeste frekvenstegn er:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Hun ser ost";
printf ("str1:% s", str5);
printf ("Det højeste frekvenstegn er:% c \ ⁠n", maxFrequencyChar (str5));
}

Produktion:

str1: Hvilken heks er hvilken?
Den højeste frekvens er: h
str2: Han kastede tre straffekast
Den højeste frekvens er: e
str3: Eddie redigerede det
Den højeste frekvens er: d
str4: Makeuseof
Den højeste frekvens er: e
str5: Hun ser ost
Den højeste frekvens er: e

JavaScript-program til at finde karakteren med den højeste frekvens

Nedenfor er JavaScript-programmet til at finde tegnet med den højeste frekvens i en streng:

// JavaScript-program for at finde tegnet
// har den højeste frekvens i en streng
lad ASCII_SIZE = 256;
funktion maxFrequencyChar (str)
{
// Array for at gemme hyppigheden af ​​hvert tegn
// Initialiserede hyppigheden af ​​hvert tegn som 0
lad frekvens = ny matrix (ASCII_SIZE);
for (lad i = 0; i {
frekvens [i] = 0;
}
// Find længde af inputstrengen
lad lenOfStr = str.længde;
for (lad i = 0; i {
frekvens [str [i] .charCodeAt (0)] + = 1;
}
// Initialiser maxFrequency-variablen
lad maxFrequency = -1;
// Initialiser variablen maxFrequencyChar
lad maxFrequencyChar = '';
// Traversering og vedligeholdelse af
// hyppigheden af ​​hvert tegn
for (lad i = 0; i {
hvis (maxFrequency {
maxFrequency = frekvens [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Førerkode
let str1 = "Hvilken heks er hvilken?";
document.write ("str1:" + str1 + "
");
document.write ("Det højeste frekvenstegn er:" + maxFrequencyChar (str1) + "
")
let str2 = "Han kastede tre straffekast";
document.write ("str2:" + str2 + "
");
document.write ("Det højeste frekvenstegn er:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie redigerede det";
document.write ("str3:" + str3 + "
");
document.write ("Det højeste frekvenstegn er:" + maxFrequencyChar (str3) + "
")
lad str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Det højeste frekvenstegn er:" + maxFrequencyChar (str4) + "
")
let str5 = "Hun ser ost";
document.write ("str5:" + str5 + "
");
document.write ("Det højeste frekvenstegn er:" + maxFrequencyChar (str5) + "
")

Produktion:

str1: Hvilken heks er hvilken?
Den højeste frekvens er: h
str2: Han kastede tre straffekast
Den højeste frekvens er: e
str3: Eddie redigerede det
Den højeste frekvens er: d
str4: Makeuseof
Den højeste frekvens er: e
str5: Hun ser ost
Den højeste frekvens er: e

Analyser tid og rumkompleksitet

Tidenes kompleksitet af maxFrequencyChar () funktion er På). Rumets kompleksitet af maxFrequencyChar () funktion er O (1) som et fast mellemrum (Hash-array). Det afhænger ikke af inputstrengens størrelse.

Big-O-notation giver dig en måde at beregne, hvor lang tid det tager at køre din kode. Det er et af de vigtigste begreber til analyse af algoritmer. Hvis du er programmør, skal du vide om Big-O Notation.

Yuvraj Chandra (30 artikler udgivet)

Yuvraj er en bachelorstudent i datalogi ved University of Delhi, Indien. Han brænder for Full Stack Webudvikling. Når han ikke skriver, udforsker han dybden af ​​forskellige teknologier.

Mere fra Yuvraj Chandra