Ako nájsť najčastejšie sa vyskytujúci znak v reťazci

Struny sú veľmi dôležitou témou pri programovaní rozhovorov. Pred rozhovormi je rozumné precvičiť si niektoré problémy s programovaním zamerané na struny. V tomto článku sa dozviete, ako nájsť najčastejšie sa vyskytujúci znak v reťazci.

Príklady na pochopenie problému

Príklad 1: Nech je daný reťazec „Makeuseof“. Znak „e“ sa v danom reťazci vyskytuje dvakrát a všetky ostatné znaky sa vyskytujú iba raz. Znak „e“ má teda najvyššiu frekvenciu v danom reťazci.

Príklad 2: Nech je daný reťazec „Vidí syr“. Znak „e“ sa v danom reťazci vyskytuje 6-krát a všetky ostatné znaky sa vyskytujú menej ako 6-krát. Znak „e“ má teda najvyššiu frekvenciu v danom reťazci.

Prístup k nájdeniu najčastejšie sa vyskytujúcej postavy v reťazci

Technika hash je najefektívnejším spôsobom, ako nájsť znak s najvyššou frekvenciou v reťazci. V tejto technike sa prechádza reťazcom a každý znak reťazca sa hašuje do poľa znakov ASCII.

Nech je vstupný reťazec „Makeuseof“, každý znak tohto reťazca je hašovaný takto:

frekvencia ['M'] = 1

frekvencia ['a] = 1

frekvencia ['k'] = 1

frekvencia ['e'] = 2

frekvencia ['u'] = 1

frekvencia ['s'] = 1

frekvencia ['o'] = 1

frekvencia ['f'] = 1

Vráti sa index maximálnej hodnoty vo frekvenčnom poli. Tu 2 je najvyššia hodnota, preto sa vráti „e“.

Program C ++ na vyhľadanie znaku s najvyššou frekvenciou

Nižšie je uvedený program C ++ na vyhľadanie znaku s najvyššou frekvenciou v reťazci:

Súvisiace: Ako počítať výskyty danej postavy v reťazci

// Program C ++ na vyhľadanie znaku
// s najvyššou frekvenciou v reťazci
#include 
#include 
#define ASCII_SIZE 256
pomocou namespace std;
char maxFrequencyChar (reťazec str)
{
// Pole na uloženie frekvencie jednotlivých znakov
// Inicializovala frekvenciu každého znaku ako 0
frekvencia int [ASCII_SIZE] = {0};
// Nájdenie dĺžky vstupného reťazca
int lenOfStr = str.length ();
// Inicializuje premennú maxFrequency
int maxFrequency = -1;
// Inicializuje premennú maxFrequencyChar
char maxFrequencyChar;
// Posuv a údržba
// frekvencia jednotlivých znakov
pre (int i = 0; i {
frekvencia [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvencia [str [i]];
maxFrequencyChar = str [i];
}
}
návrat maxFrequencyChar;
}
// Kód ovládača
int main ()
{
string str1 = "Ktorá čarodejnica je ktorá?";
cout << "str1:" << str1 << endl;
cout << "Znak s najvyššou frekvenciou je:" << maxFrequencyChar (str1) << endl;
string str2 = "Vyhodil tri trestné hody";
cout << "str2:" << str2 << endl;
cout << "Znak s najvyššou frekvenciou je:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie to upravil";
cout << "str3:" << str3 << endl;
cout << "Znak s najvyššou frekvenciou je:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Znak s najvyššou frekvenciou je:" << maxFrequencyChar (str4) << endl;
string str5 = "Vidí syr";
cout << "str5:" << str5 << endl;
cout << "Znak s najvyššou frekvenciou je:" << maxFrequencyChar (str5) << endl;
}

Výkon:

str1: Ktorá čarodejnica je ktorá?
Najvyšší znak frekvencie je: h
str2: Hodil tri trestné hody
Najvyšší znak frekvencie je: e
str3: Eddie to upravil
Najvyšší znak frekvencie je: d
str4: Makeuseof
Najvyšší znak frekvencie je: e
str5: Vidí syr
Najvyšší znak frekvencie je: e

Program v jazyku Python na vyhľadanie znaku s najvyššou frekvenciou

Ďalej uvádzame program Python na vyhľadanie znaku s najvyššou frekvenciou v reťazci:

Súvisiace: Ako obrátiť reťazec v C ++, Python a JavaScript

# Program v Pythone na vyhľadanie znaku
# s najvyššou frekvenciou v reťazci
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Pole na uloženie frekvencie jednotlivých znakov
# Inicializovala frekvenciu každého znaku ako 0
frekvencia = [0] * ASCII_SIZE
# Inicializujte premennú maxFrequency
maxFrequency = -1
# Inicializujte premennú maxFrequencyChar
maxFrequencyChar = ''
# Traverzovanie a údržba
# frekvencia jednotlivých znakov
pre i v str:
frekvencia [ord (i)] + = 1
pre i v str:
ak maxFrekvencia maxFrequency = frequency [ord (i)]
maxFrequencyChar = i
návrat maxFrequencyChar
# Kód ovládača
str1 = "Ktorá čarodejnica je ktorá?"
print ("str1:", str1)
print ("Najvyšší znak frekvencie je:", maxFrequencyChar (str1))
str2 = "Vyhodil tri trestné hody"
print ("str2:", str2)
print ("Najvyšší znak frekvencie je:", maxFrequencyChar (str2))
str3 = "Eddie to upravil"
print ("str3:", str3)
print ("Najvyšší znak frekvencie je:", maxFrequencyChar (str3))
str4 = "Makeuseof"
print ("str4:", str4)
print ("Znak s najvyššou frekvenciou je:", maxFrequencyChar (str4))
str5 = "Vidí syr"
print ("str5:", str5)
print ("Najvyšší znak frekvencie je:", maxFrequencyChar (str5))

Výkon:

str1: Ktorá čarodejnica je ktorá?
Najvyšší znak frekvencie je: h
str2: Hodil tri trestné hody
Najvyšší znak frekvencie je: e
str3: Eddie to upravil
Najvyšší znak frekvencie je: d
str4: Makeuseof
Najvyšší znak frekvencie je: e
str5: Vidí syr
Najvyšší znak frekvencie je: e

Program C na vyhľadanie postavy s najvyššou frekvenciou

Nižšie je uvedený program C na vyhľadanie znaku s najvyššou frekvenciou v reťazci:

Súvisiace: Ako nájsť samohlásky, spoluhlásky, číslice a špeciálne znaky v reťazci

// Program C na vyhľadanie znaku
// s najvyššou frekvenciou v reťazci
#include 
#include 
#define ASCII_SIZE 256
pomocou namespace std;
char maxFrequencyChar (char * str)
{
// Pole na uloženie frekvencie jednotlivých znakov
// Inicializovala frekvenciu každého znaku ako 0
frekvencia int [ASCII_SIZE] = {0};
// Nájdenie dĺžky vstupného reťazca
int lenOfStr = strlen (str);
// Inicializuje premennú maxFrequency
int maxFrequency = 0;
// Inicializuje premennú maxFrequencyChar
char maxFrequencyChar;
// Posuv a údržba
// frekvencia jednotlivých znakov
pre (int i = 0; i {
frekvencia [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvencia [str [i]];
maxFrequencyChar = str [i];
}
}
návrat maxFrequencyChar;
}
// Kód ovládača
int main ()
{
char str1 [] = "Ktorá čarodejnica je ktorá?";
printf ("str1:% s", str1);
printf ("Znak s najvyššou frekvenciou je:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Vyhodil tri trestné hody";
printf ("str2:% s", str2);
printf ("Znak s najvyššou frekvenciou je:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie to upravil";
printf ("str3:% s", str3);
printf ("Znak s najvyššou frekvenciou je:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Znak s najvyššou frekvenciou je:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Vidí syr";
printf ("str1:% s", str5);
printf ("Znak s najvyššou frekvenciou je:% c \ ⁠n", maxFrequencyChar (str5));
}

Výkon:

str1: Ktorá čarodejnica je ktorá?
Najvyšší znak frekvencie je: h
str2: Hodil tri trestné hody
Najvyšší znak frekvencie je: e
str3: Eddie to upravil
Najvyšší znak frekvencie je: d
str4: Makeuseof
Najvyšší znak frekvencie je: e
str5: Vidí syr
Najvyšší znak frekvencie je: e

Program JavaScript na vyhľadanie znaku s najvyššou frekvenciou

Nižšie je uvedený program JavaScript, ktorý umožňuje nájsť znak s najvyššou frekvenciou v reťazci:

// Program JavaScript na vyhľadanie znaku
// s najvyššou frekvenciou v reťazci
nech ASCII_SIZE = 256;
funkcia maxFrequencyChar (str)
{
// Pole na uloženie frekvencie jednotlivých znakov
// Inicializovala frekvenciu každého znaku ako 0
let frequency = new Array (ASCII_SIZE);
pre (nech i = 0; i {
frekvencia [i] = 0;
}
// Nájdenie dĺžky vstupného reťazca
nech lenOfStr = str.length;
pre (nech i = 0; i {
frekvencia [str [i] .charCodeAt (0)] + = 1;
}
// Inicializuje premennú maxFrequency
nech maxFrequency = -1;
// Inicializuje premennú maxFrequencyChar
nech maxFrequencyChar = '';
// Posuv a údržba
// frekvencia jednotlivých znakov
pre (nech i = 0; i {
if (maxFrequency {
maxFrequency = frequency [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
návrat maxFrequencyChar;
}
// Kód ovládača
nech str1 = "Ktorá čarodejnica je ktorá?";
document.write ("str1:" + str1 + "
");
document.write ("Znak s najvyššou frekvenciou je:" + maxFrequencyChar (str1) + "
")
nech str2 = "Vyhodil tri trestné hody";
document.write ("str2:" + str2 + "
");
document.write ("Znak s najvyššou frekvenciou je:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie to upravil";
document.write ("str3:" + str3 + "
");
document.write ("Najvyšší znak frekvencie je:" + maxFrequencyChar (str3) + "
")
nech str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Znak s najvyššou frekvenciou je:" + maxFrequencyChar (str4) + "
")
nech str5 = "Vidí syr";
document.write ("str5:" + str5 + "
");
document.write ("Najvyšší znak frekvencie je:" + maxFrequencyChar (str5) + "
")

Výkon:

str1: Ktorá čarodejnica je ktorá?
Najvyšší znak frekvencie je: h
str2: Hodil tri trestné hody
Najvyšší znak frekvencie je: e
str3: Eddie to upravil
Najvyšší znak frekvencie je: d
str4: Makeuseof
Najvyšší znak frekvencie je: e
str5: Vidí syr
Najvyšší znak frekvencie je: e

Analyzujte časovú a vesmírnu zložitosť

Časová zložitosť maxFrequencyChar () funkcia je O (n). Priestorová zložitosť maxFrequencyChar () funkcia je O (1) ako pevný priestor (hashovacie pole). Nezávisí to od veľkosti vstupného reťazca.

Big-O notácia vám dáva spôsob, ako vypočítať, ako dlho bude trvať spustenie vášho kódu. Je to jeden z najdôležitejších konceptov pre analýzu algoritmov. Ak ste programátor, musíte vedieť o značke Big-O.

Yuvraj Chandra (30 publikovaných článkov)

Yuvraj je vysokoškolský študent v odbore počítačových vied na indickej univerzite v Dillí. Je vášnivý pre vývoj webových stránok na princípe Full Stack. Ak nepíše, skúma hĺbku rôznych technológií.

Viac od Yuvraja Chandru