Jak najít nejčastěji se vyskytující znak v řetězci

Řetězce jsou velmi důležitým tématem při programování rozhovorů. Je rozumné si před pohovory procvičit některé problémy s programováním zaměřené na struny. V tomto článku se dozvíte, jak najít nejčastěji se vyskytující znak v řetězci.

Příklady k pochopení problému

Příklad 1: Nechte daný řetězec být „Makeuseof“. Znak 'e' se v daném řetězci vyskytuje dvakrát a všechny ostatní znaky se vyskytují pouze jednou. Znak 'e' má tedy nejvyšší frekvenci v daném řetězci.

Příklad 2: Nechť daný řetězec bude „Vidí sýr“. Znak 'e' se v daném řetězci vyskytuje 6krát a všechny ostatní znaky se vyskytují méně než 6krát. Znak 'e' má tedy nejvyšší frekvenci v daném řetězci.

Přístup k vyhledání nejčastěji se vyskytující postavy v řetězci

Technika hašování je nejúčinnějším způsobem, jak najít postavu s nejvyšší frekvencí v řetězci. V této technice je řetězec prochází a každý znak řetězce je hašován do pole znaků ASCII.

Nechte vstupní řetězec být „Makeuseof“, každý znak tohoto řetězce je hašován následovně:

frekvence ['M'] = 1

frekvence ['a] = 1

frekvence ['k'] = 1

frekvence ['e'] = 2

frekvence ['u'] = 1

frekvence ['s'] = 1

frekvence ['o'] = 1

frekvence ['f'] = 1

Vrátí se index maximální hodnoty ve frekvenčním poli. Tady 2 je nejvyšší hodnota, proto se vrací „e“.

Program C ++ pro vyhledání postavy s nejvyšší frekvencí

Níže je program C ++ k vyhledání znaku s nejvyšší frekvencí v řetězci:

Příbuzný: Jak spočítat výskyt dané postavy v řetězci

// Program C ++ k vyhledání znaku
// mající nejvyšší frekvenci v řetězci
#zahrnout 
#zahrnout 
#define ASCII_SIZE 256
pomocí jmenného prostoru std;
char maxFrequencyChar (str řetězec)
{
// Pole pro uložení frekvence jednotlivých znaků
// Inicializoval frekvenci každého znaku jako 0
frekvence int [ASCII_SIZE] = {0};
// Nalezení délky vstupního řetězce
int lenOfStr = str.length ();
// Inicializace proměnné maxFrequency
int maxFrequency = -1;
// Inicializace proměnné maxFrequencyChar
char maxFrequencyChar;
// Procházení a údržba
// frekvence jednotlivých znaků
pro (int i = 0; i {
frekvence [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvence [str [i]];
maxFrequencyChar = str [i];
}
}
návrat maxFrequencyChar;
}
// Kód ovladače
int main ()
{
string str1 = "Která čarodějnice je která?";
cout << "str1:" << str1 << endl;
cout << "Znak nejvyšší frekvence je:" << maxFrequencyChar (str1) << endl;
string str2 = "Hodil tři trestné hody";
cout << "str2:" << str2 << endl;
cout << "Znak nejvyšší frekvence je:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie to upravil";
cout << "str3:" << str3 << endl;
cout << "Znak nejvyšší frekvence je:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Znak nejvyšší frekvence je:" << maxFrequencyChar (str4) << endl;
string str5 = "Vidí sýr";
cout << "str5:" << str5 << endl;
cout << "Znak nejvyšší frekvence je:" << maxFrequencyChar (str5) << endl;
}

Výstup:

str1: Která čarodějnice je která?
Nejvyšší znak frekvence je: h
str2: Hodil tři trestné hody
Nejvyšší kmitočtový znak je: e
str3: Eddie to upravil
Nejvyšší znak frekvence je: d
str4: Makeuseof
Nejvyšší kmitočtový znak je: e
str5: Vidí sýr
Nejvyšší kmitočtový znak je: e

Program v Pythonu k vyhledání postavy s nejvyšší frekvencí

Níže je program Python k vyhledání postavy s nejvyšší frekvencí v řetězci:

Příbuzný: Jak převrátit řetězec v C ++, Pythonu a JavaScriptu

# Program v Pythonu k vyhledání postavy
# mající nejvyšší frekvenci v řetězci
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Pole pro uložení frekvence jednotlivých znaků
# Inicializoval frekvenci každého znaku jako 0
frekvence = [0] * ASCII_SIZE
# Inicializovat proměnnou maxFrequency
maxFrequency = -1
# Inicializovat proměnnou maxFrequencyChar
maxFrequencyChar = ''
# Procházení a údržba
# frekvence jednotlivých znaků
pro i v str:
frekvence [ord (i)] + = 1
pro i v str:
pokud maxFrequency maxFrequency = frekvence [ord (i)]
maxFrequencyChar = i
vrátit maxFrequencyChar
# Kód ovladače
str1 = "Která čarodějnice je která?"
print ("str1:", str1)
print ("Znak nejvyšší frekvence je:", maxFrequencyChar (str1))
str2 = "Hodil tři trestné hody"
print ("str2:", str2)
print ("Znak nejvyšší frekvence je:", maxFrequencyChar (str2))
str3 = "Eddie to upravil"
print ("str3:", str3)
print ("Znak nejvyšší frekvence je:", maxFrequencyChar (str3))
str4 = "Makeuseof"
print ("str4:", str4)
print ("Znak nejvyšší frekvence je:", maxFrequencyChar (str4))
str5 = "Vidí sýr"
print ("str5:", str5)
print ("Znak nejvyšší frekvence je:", maxFrequencyChar (str5))

Výstup:

str1: Která čarodějnice je která?
Nejvyšší znak frekvence je: h
str2: Hodil tři trestné hody
Nejvyšší kmitočtový znak je: e
str3: Eddie to upravil
Nejvyšší znak frekvence je: d
str4: Makeuseof
Nejvyšší kmitočtový znak je: e
str5: Vidí sýr
Nejvyšší kmitočtový znak je: e

C Program pro vyhledání postavy s nejvyšší frekvencí

Níže je program C pro vyhledání postavy s nejvyšší frekvencí v řetězci:

Příbuzný: Jak najít samohlásky, souhlásky, číslice a speciální znaky v řetězci

// Program C k vyhledání znaku
// mající nejvyšší frekvenci v řetězci
#zahrnout 
#zahrnout 
#define ASCII_SIZE 256
pomocí jmenného prostoru std;
char maxFrequencyChar (char * str)
{
// Pole pro uložení frekvence jednotlivých znaků
// Inicializoval frekvenci každého znaku jako 0
frekvence int [ASCII_SIZE] = {0};
// Nalezení délky vstupního řetězce
int lenOfStr = strlen (str);
// Inicializace proměnné maxFrequency
int maxFrequency = 0;
// Inicializace proměnné maxFrequencyChar
char maxFrequencyChar;
// Procházení a údržba
// frekvence jednotlivých znaků
pro (int i = 0; i {
frekvence [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvence [str [i]];
maxFrequencyChar = str [i];
}
}
návrat maxFrequencyChar;
}
// Kód ovladače
int main ()
{
char str1 [] = "Která čarodějnice je která?";
printf ("str1:% s", str1);
printf ("Znak nejvyšší frekvence je:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Hodil tři trestné hody";
printf ("str2:% s", str2);
printf ("Znak nejvyšší frekvence je:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie to upravil";
printf ("str3:% s", str3);
printf ("Znak nejvyšší frekvence je:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Znak nejvyšší frekvence je:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Vidí sýr";
printf ("str1:% s", str5);
printf ("Nejvyšší znak frekvence je:% c \ ⁠n", maxFrequencyChar (str5));
}

Výstup:

str1: Která čarodějnice je která?
Nejvyšší znak frekvence je: h
str2: Hodil tři trestné hody
Nejvyšší kmitočtový znak je: e
str3: Eddie to upravil
Nejvyšší znak frekvence je: d
str4: Makeuseof
Nejvyšší kmitočtový znak je: e
str5: Vidí sýr
Nejvyšší kmitočtový znak je: e

Program JavaScript k vyhledání postavy s nejvyšší frekvencí

Níže je uveden program JavaScriptu k vyhledání znaku s nejvyšší frekvencí v řetězci:

// JavaScriptový program pro vyhledání znaku
// mající nejvyšší frekvenci v řetězci
nechme ASCII_SIZE = 256;
funkce maxFrequencyChar (str)
{
// Pole pro uložení frekvence jednotlivých znaků
// Inicializoval frekvenci každého znaku jako 0
let frequency = new Array (ASCII_SIZE);
pro (ať i = 0; i {
frekvence [i] = 0;
}
// Nalezení délky vstupního řetězce
nechť lenOfStr = str.length;
pro (ať i = 0; i {
frekvence [str [i] .charCodeAt (0)] + = 1;
}
// Inicializace proměnné maxFrequency
nechme maxFrequency = -1;
// Inicializace proměnné maxFrequencyChar
nechme maxFrequencyChar = '';
// Procházení a údržba
// frekvence jednotlivých znaků
pro (ať i = 0; i {
if (maxFrequency {
maxFrequency = frekvence [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
návrat maxFrequencyChar;
}
// Kód ovladače
let str1 = "Která čarodějnice je která?";
document.write ("str1:" + str1 + "
");
document.write ("Znak nejvyšší frekvence je:" + maxFrequencyChar (str1) + "
")
let str2 = "Hodil tři trestné hody";
document.write ("str2:" + str2 + "
");
document.write ("Znak nejvyšší frekvence je:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie to upravil";
document.write ("str3:" + str3 + "
");
document.write ("Znak nejvyšší frekvence je:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Znak nejvyšší frekvence je:" + maxFrequencyChar (str4) + "
")
let str5 = "Vidí sýr";
document.write ("str5:" + str5 + "
");
document.write ("Znak nejvyšší frekvence je:" + maxFrequencyChar (str5) + "
")

Výstup:

str1: Která čarodějnice je která?
Nejvyšší znak frekvence je: h
str2: Hodil tři trestné hody
Nejvyšší kmitočtový znak je: e
str3: Eddie to upravil
Nejvyšší znak frekvence je: d
str4: Makeuseof
Nejvyšší kmitočtový znak je: e
str5: Vidí sýr
Nejvyšší kmitočtový znak je: e

Analyzujte časoprostorovou složitost

Časová složitost maxFrequencyChar () funkce je Na). Prostorová složitost maxFrequencyChar () funkce je O (1) jako pevný prostor (hashovací pole). Nezáleží na velikosti vstupního řetězce.

Big-O notace vám dává způsob, jak vypočítat, jak dlouho bude trvat spuštění vašeho kódu. Je to jeden z nejdůležitějších konceptů pro analýzu algoritmů. Pokud jste programátor, musíte vědět o Big-O Notation.

Yuvraj Chandra (30 článků publikováno)

Yuvraj je vysokoškolský student výpočetní techniky na univerzitě v Dillí v Indii. Je vášnivým vývojářem Full Stack Web Development. Když nepíše, zkoumá hloubku různých technologií.

Více od Yuvraj Chandra