Hogyan lehet megtalálni a leggyakrabban előforduló karaktert egy húrban

A húrok nagyon fontos téma az interjúk programozásában. Bölcs dolog interjúk előtt gyakorolni néhány, a húrokra összpontosító programozási problémát. Ebben a cikkben megtudhatja, hogyan lehet megtalálni a karakterlánc leggyakrabban előforduló karakterét.

Példák a probléma megértésére

1. példa: Legyen a megadott karakterlánc "Makeuseof". Az 'e' karakter kétszer fordul elő az adott karakterláncban, és az összes többi karakter csak egyszer fordul elő. Így az 'e' karakter rendelkezik a legnagyobb gyakorisággal az adott karakterláncban.

2. példa: Legyen a megadott karakterlánc "Ő sajtot lát". Az 'e' karakter 6-szor fordul elő az adott karakterláncban, az összes többi karakter pedig kevesebb mint 6-szor fordul elő. Így az 'e' karakter rendelkezik a legnagyobb gyakorisággal az adott karakterláncban.

Megközelítés a karakterlánc leggyakrabban előforduló karakterének megtalálásához

A hashing technika a leghatékonyabb módja annak, hogy megtalálja azt a karaktert, amelynek a frekvenciája a legmagasabb. Ebben a technikában a karakterláncot bejárják, és a karakterlánc minden egyes karakterét ASCII karakterek tömbjévé alakítják.

Legyen a beviteli karakterlánc "Makeuseof", a karakterlánc minden karakterét a következőképpen hasítják el:

gyakoriság ['M'] = 1

gyakoriság ['a] = 1

gyakoriság ['k'] = 1

gyakoriság ['e'] = 2

gyakoriság ['u'] = 1

gyakoriság ['s'] = 1

gyakoriság ['o'] = 1

gyakoriság ['f'] = 1

Visszaadja a frekvenciatömb maximális értékének indexét. Itt 2 a legmagasabb érték, ezért az 'e' adódik vissza.

C ++ program a legmagasabb gyakorisággal rendelkező karakter megkeresésére

Az alábbiakban a C ++ program található a karakterláncban a legnagyobb gyakorisággal rendelkező karakter megkeresésére:

Összefüggő: Hogyan számoljuk meg egy adott karakter előfordulását egy húrban

// C ++ program a karakter megkereséséhez
// a karakterláncban a legnagyobb a frekvencia
#include 
#include 
#define ASCII_SIZE 256
névtér használata std;
char maxFrequencyChar (string karakterlánc)
{
// Az egyes karakterek gyakoriságának tárolására szolgáló tömb
// Minden karakter gyakoriságát inicializálta 0-ként
int frekvencia [ASCII_SIZE] = {0};
// A bemeneti karakterlánc hosszának megkeresése
int lenOfStr = str.hossz ();
// A maxFrequency változó inicializálása
int maxFrekvencia = -1;
// A maxFrequencyChar változó inicializálása
char maxFrequencyChar;
// A. Áthaladása és karbantartása
// az egyes karakterek gyakorisága
for (int i = 0; i {
frekvencia [str [i]] ++;
if (maxFrekvencia {
maxFrequency = frekvencia [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Illesztőprogram-kód
int main ()
{
string str1 = "Melyik boszorkány melyik?";
cout << "str1:" << str1 << endl;
cout << "A legmagasabb frekvenciakarakter:" << maxFrequencyChar (str1) << endl;
string str2 = "Három szabaddobást dobott";
cout << "str2:" << str2 << endl;
cout << "A legmagasabb frekvenciakarakter:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie szerkesztette";
cout << "str3:" << str3 << endl;
cout << "A legmagasabb frekvenciakarakter:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "A legmagasabb frekvenciakarakter:" << maxFrequencyChar (str4) << endl;
string str5 = "Sajtot lát";
cout << "str5:" << str5 << endl;
cout << "A legmagasabb frekvenciakarakter:" << maxFrequencyChar (str5) << endl;
}

Kimenet:

str1: Melyik boszorkány melyik?
A legmagasabb frekvenciakarakter: h
str2: Három szabaddobást dobott
A legmagasabb frekvenciakarakter: e
str3: Eddie szerkesztette
A legmagasabb frekvenciakarakter: d
str4: Használat
A legmagasabb frekvenciakarakter: e
str5: Sajtot lát
A legmagasabb frekvenciakarakter: e

Python program a legnagyobb gyakorisággal rendelkező karakter megkeresésére

Az alábbiakban a Python program található a karakterláncban a legnagyobb gyakorisággal rendelkező karakter megkeresésére:

Összefüggő: Hogyan lehet megfordítani egy karakterláncot a C ++, a Python és a JavaScript programokban

# Python program a karakter megtalálásához
# a legmagasabb frekvenciával rendelkezik egy karakterláncban
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Tömb az egyes karakterek gyakoriságának tárolására
# Inicializálta az egyes karakterek gyakoriságát 0-ra
gyakoriság = [0] * ASCII_SIZE
# A maxFrequency változó inicializálása
maxFrekvencia = -1
# A maxFrequencyChar változó inicializálása
maxFrequencyChar = ""
# A. Áthaladása és fenntartása
# az egyes karakterek gyakorisága
mert i in str:
gyakoriság [ord (i)] + = 1
mert i in str:
ha maxFrequency maxFrequency = frekvencia [ord (i)]
maxFrequencyChar = i
return maxFrequencyChar
# Illesztőprogram-kód
str1 = "Melyik boszorkány melyik?"
nyomtatás ("str1:", str1)
print ("A legmagasabb frekvenciakarakter:", maxFrequencyChar (str1))
str2 = "Három szabaddobást dobott"
nyomtatás ("str2:", str2)
print ("A legmagasabb frekvencia karakter:", maxFrequencyChar (str2))
str3 = "Eddie szerkesztette"
nyomtatás ("str3:", str3)
print ("A legmagasabb frekvenciakarakter:", maxFrequencyChar (str3))
str4 = "Használat"
nyomtatás ("str4:", str4)
print ("A legmagasabb frekvenciakarakter:", maxFrequencyChar (str4))
str5 = "Sajtot lát"
nyomtatás ("str5:", str5)
print ("A legmagasabb frekvenciakarakter:", maxFrequencyChar (str5))

Kimenet:

str1: Melyik boszorkány melyik?
A legmagasabb frekvenciakarakter: h
str2: Három szabaddobást dobott
A legmagasabb frekvenciakarakter: e
str3: Eddie szerkesztette
A legmagasabb frekvenciakarakter: d
str4: Használat
A legmagasabb frekvenciakarakter: e
str5: Sajtot lát
A legmagasabb frekvenciakarakter: e

C Program a legmagasabb frekvenciájú karakter megkeresésére

Az alábbiakban a C program található a karakterláncban a legmagasabb gyakorisággal:

Összefüggő: Hogyan lehet magánhangzókat, mássalhangzókat, számokat és különleges karaktereket találni egy karakterláncban?

// C program a karakter megtalálásához
// a karakterláncban a legnagyobb a frekvencia
#include 
#include 
#define ASCII_SIZE 256
névtér használata std;
char maxFrequencyChar (char * str)
{
// Az egyes karakterek gyakoriságának tárolására szolgáló tömb
// Minden karakter gyakoriságát inicializálta 0-ként
int frekvencia [ASCII_SIZE] = {0};
// A bemeneti karakterlánc hosszának megkeresése
int lenOfStr = strlen (str);
// A maxFrequency változó inicializálása
int maxFrekvencia = 0;
// A maxFrequencyChar változó inicializálása
char maxFrequencyChar;
// A. Áthaladása és karbantartása
// az egyes karakterek gyakorisága
for (int i = 0; i {
frekvencia [str [i]] ++;
if (maxFrekvencia {
maxFrequency = frekvencia [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Illesztőprogram-kód
int main ()
{
char str1 [] = "Melyik boszorkány melyik?";
printf ("str1:% s", str1);
printf ("A legmagasabb frekvenciakarakter:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Három szabaddobást dobott";
printf ("str2:% s", str2);
printf ("A legmagasabb frekvenciakarakter:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie szerkesztette";
printf ("str3:% s", str3);
printf ("A legmagasabb frekvenciakarakter:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("A legmagasabb frekvenciakarakter:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Sajtot lát";
printf ("str1:% s", str5);
printf ("A legmagasabb frekvenciakarakter:% c \ ⁠n", maxFrequencyChar (str5));
}

Kimenet:

str1: Melyik boszorkány melyik?
A legmagasabb frekvenciakarakter: h
str2: Három szabaddobást dobott
A legmagasabb frekvenciakarakter: e
str3: Eddie szerkesztette
A legmagasabb frekvenciakarakter: d
str4: Használat
A legmagasabb frekvenciakarakter: e
str5: Sajtot lát
A legmagasabb frekvenciakarakter: e

JavaScript program a legmagasabb gyakoriságú karakter megtalálásához

Az alábbiakban a JavaScript program található a karakterláncban a legmagasabb gyakorisággal:

// JavaScript program a karakter megtalálásához
// a karakterláncban a legnagyobb a frekvencia
legyen ASCII_SIZE = 256;
függvény maxFrequencyChar (str)
{
// Az egyes karakterek gyakoriságának tárolására szolgáló tömb
// Minden karakter gyakoriságát inicializálta 0-ként
let gyakorisága = új tömb (ASCII_SIZE);
for (legyen i = 0; i {
frekvencia [i] = 0;
}
// A bemeneti karakterlánc hosszának megkeresése
legyen lenOfStr = str.hossz;
for (legyen i = 0; i {
frekvencia [str [i] .charCodeAt (0)] + = 1;
}
// A maxFrequency változó inicializálása
legyen maxFrekvencia = -1;
// A maxFrequencyChar változó inicializálása
legyen maxFrequencyChar = "";
// A. Áthaladása és karbantartása
// az egyes karakterek gyakorisága
for (legyen i = 0; i {
if (maxFrequency {
maxFrequency = frekvencia [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Illesztőprogram-kód
legyen str1 = "Melyik boszorkány melyik?";
document.write ("str1:" + str1 + "
");
document.write ("A legmagasabb frekvenciakarakter:" + maxFrequencyChar (str1) + "
")
let str2 = "Három szabaddobást dobott";
document.write ("str2:" + str2 + "
");
document.write ("A legmagasabb frekvenciakarakter:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie szerkesztette";
document.write ("str3:" + str3 + "
");
document.write ("A legmagasabb frekvenciakarakter:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("A legmagasabb frekvenciakarakter:" + maxFrequencyChar (str4) + "
")
let str5 = "Látja a sajtot";
document.write ("str5:" + str5 + "
");
document.write ("A legmagasabb frekvenciakarakter:" + maxFrequencyChar (str5) + "
")

Kimenet:

str1: Melyik boszorkány melyik?
A legmagasabb frekvenciakarakter: h
str2: Három szabaddobást dobott
A legmagasabb frekvenciakarakter: e
str3: Eddie szerkesztette
A legmagasabb frekvenciakarakter: d
str4: Használat
A legmagasabb frekvenciakarakter: e
str5: Sajtot lát
A legmagasabb frekvenciakarakter: e

Elemezze az idő és a tér komplexitását

Az idő összetettsége maxFrequencyChar () funkció az Tovább). A tér bonyolultsága maxFrequencyChar () funkció az O (1) rögzített térként (Hash tömb). Ez nem függ a bemeneti karakterlánc méretétől.

A Big-O jelölés segítségével kiszámíthatja, hogy mennyi időbe telik a kód futtatása. Ez az egyik legfontosabb fogalom az algoritmusok elemzéséhez. Ha programozó vagy, akkor tudnod kell a Big-O Notationról.

Yuvraj Chandra (30 cikk megjelent)

Yuvraj informatikus egyetemi hallgató az indiai Delhi Egyetemen. Szenvedélyes a Full Stack webfejlesztés iránt. Amikor nem ír, a különböző technológiák mélységét kutatja.

Többet Yuvraj Chandrától