Kako najti najpogostejši lik v nizu

Strune so zelo pomembna tema v programskih intervjujih. Pred intervjuji je pametno vaditi nekaj težav s programiranjem, osredotočenih na strune. V tem članku boste izvedeli, kako najti najpogostejši znak v nizu.

Primeri za razumevanje problema

Primer 1: Naj bo dani niz "Makeuseof". Znak 'e' se v danem nizu pojavi dvakrat, vsi drugi znaki pa le enkrat. Tako ima znak 'e' najvišjo frekvenco v danem nizu.

2. primer: Naj bo dani niz "Ona vidi sir". Znak 'e' se v danem nizu pojavi 6-krat, vsi drugi znaki pa se pojavijo manj kot 6-krat. Tako ima znak 'e' najvišjo frekvenco v danem nizu.

Pristop k iskanju najpogostejšega lika v nizu

Tehnika razprševanja je najučinkovitejši način za iskanje znaka z najvišjo frekvenco v nizu. Pri tej tehniki se niz prečka in vsak znak niza razprši v niz znakov ASCII.

Vhodni niz naj bo "Makeuseof", vsak znak tega niza je zgoščen, kot sledi:

frekvenca ['M'] = 1

frekvenca ['a] = 1

frekvenca ['k'] = 1

frekvenca ['e'] = 2

frekvenca ['u'] = 1

frekvenca ['s'] = 1

frekvenca ['o'] = 1

frekvenca ['f'] = 1

Vrne se indeks največje vrednosti v frekvenčnem polju. Tukaj 2 je najvišja vrednost, zato se vrne 'e'.

Program C ++ za iskanje znakov z najvišjo frekvenco

Spodaj je program C ++ za iskanje znaka z najvišjo frekvenco v nizu:

Sorodno: Kako prešteti pojavitve danega lika v nizu

// program C ++ za iskanje znaka
// z najvišjo frekvenco v nizu
#include 
#include 
#define ASCII_SIZE 256
uporaba imenskega prostora std;
char maxFrequencyChar (niz str)
{
// Matrika za shranjevanje frekvence posameznih znakov
// Inicializirala je pogostost vsakega znaka kot 0
int frekvenca [ASCII_SIZE] = {0};
// Iskanje dolžine vhodnega niza
int lenOfStr = str.length ();
// Inicializiramo spremenljivko maxFrequency
int maxFrequency = -1;
// Inicializiramo spremenljivko maxFrequencyChar
char maxFrequencyChar;
// Prehod in vzdrževanje
// pogostost posameznih znakov
za (int i = 0; i {
frekvenca [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvenca [str [i]];
maxFrequencyChar = str [i];
}
}
vrne maxFrequencyChar;
}
// Koda voznika
int main ()
{
string str1 = "Katera čarovnica je katera?";
cout << "str1:" << str1 << endl;
cout << "Znak z najvišjo frekvenco je:" << maxFrequencyChar (str1) << endl;
string str2 = "Izvedel je tri proste mete";
cout << "str2:" << str2 << endl;
cout << "Znak z najvišjo frekvenco je:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie ga je uredil";
cout << "str3:" << str3 << endl;
cout << "Znak z najvišjo frekvenco je:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Znak z najvišjo frekvenco je:" << maxFrequencyChar (str4) << endl;
string str5 = "Ona vidi sir";
cout << "str5:" << str5 << endl;
cout << "Znak z najvišjo frekvenco je:" << maxFrequencyChar (str5) << endl;
}

Izhod:

str1: Katera čarovnica je katera?
Znak z najvišjo frekvenco je: h
str2: Izvedel je tri proste mete
Znak z najvišjo frekvenco je: e
str3: Eddie ga je uredil
Znak z najvišjo frekvenco je: d
str4: Makeuseof
Znak z najvišjo frekvenco je: e
str5: Ona vidi sir
Znak z najvišjo frekvenco je: e

Program Python za iskanje znakov z najvišjo frekvenco

Spodaj je program Python za iskanje znaka z najvišjo frekvenco v nizu:

Sorodno: Kako obrniti niz v C ++, Python in JavaScript

# Program Python za iskanje znaka
# z najvišjo frekvenco v nizu
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Matrika za shranjevanje frekvence posameznih znakov
# Inicializirala je pogostost vsakega znaka kot 0
frekvenca = [0] * ASCII_SIZE
# Inicializirajte spremenljivko maxFrequency
maxFrequency = -1
# Inicializirajte spremenljivko maxFrequencyChar
maxFrequencyChar = "
# Prehod in vzdrževanje
# pogostost posameznih znakov
za i v str:
frekvenca [ord (i)] + = 1
za i v str:
če je maxFrequency maxFrequency = frekvenca [ord (i)]
maxFrequencyChar = i
vrni maxFrequencyChar
# Koda voznika
str1 = "Katera čarovnica je katera?"
natisni ("str1:", str1)
print ("Znak z najvišjo frekvenco je:", maxFrequencyChar (str1))
str2 = "Metl je tri proste mete"
tiskanje ("str2:", str2)
print ("Znak najvišje frekvence je:", maxFrequencyChar (str2))
str3 = "Eddie jo je uredil"
natisni ("str3:", str3)
print ("Najvišji frekvenčni znak je:", maxFrequencyChar (str3))
str4 = "Izkoristi"
tiskanje ("str4:", str4)
print ("Znak najvišje frekvence je:", maxFrequencyChar (str4))
str5 = "Ona vidi sir"
tiskanje ("str5:", str5)
print ("Najfrekvenčnejši znak je:", maxFrequencyChar (str5))

Izhod:

str1: Katera čarovnica je katera?
Znak z najvišjo frekvenco je: h
str2: Izvedel je tri proste mete
Znak z najvišjo frekvenco je: e
str3: Eddie ga je uredil
Znak z najvišjo frekvenco je: d
str4: Makeuseof
Znak z najvišjo frekvenco je: e
str5: Ona vidi sir
Znak z najvišjo frekvenco je: e

Program C za iskanje lika z najvišjo frekvenco

Spodaj je program C za iskanje znaka z najvišjo frekvenco v nizu:

Sorodno: Kako najti samoglasnike, soglasnike, številke in posebne znake v nizu

// Program C za iskanje znaka
// z najvišjo frekvenco v nizu
#include 
#include 
#define ASCII_SIZE 256
uporaba imenskega prostora std;
char maxFrequencyChar (char * str)
{
// Matrika za shranjevanje frekvence posameznih znakov
// Inicializirala je pogostost vsakega znaka kot 0
int frekvenca [ASCII_SIZE] = {0};
// Iskanje dolžine vhodnega niza
int lenOfStr = strlen (str);
// Inicializiramo spremenljivko maxFrequency
int maxFrequency = 0;
// Inicializiramo spremenljivko maxFrequencyChar
char maxFrequencyChar;
// Prehod in vzdrževanje
// pogostost posameznih znakov
za (int i = 0; i {
frekvenca [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvenca [str [i]];
maxFrequencyChar = str [i];
}
}
vrne maxFrequencyChar;
}
// Koda voznika
int main ()
{
char str1 [] = "Katera čarovnica je katera?";
printf ("str1:% s", str1);
printf ("Znak najvišje frekvence je:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Izvedel je tri proste mete";
printf ("str2:% s", str2);
printf ("Znak z največjo frekvenco je:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie jo je uredil";
printf ("str3:% s", str3);
printf ("Najvišji frekvenčni znak je:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Znak najvišje frekvence je:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Ona vidi sir";
printf ("str1:% s", str5);
printf ("Najvišji frekvenčni znak je:% c \ ⁠n", maxFrequencyChar (str5));
}

Izhod:

str1: Katera čarovnica je katera?
Znak z najvišjo frekvenco je: h
str2: Izvedel je tri proste mete
Znak z najvišjo frekvenco je: e
str3: Eddie ga je uredil
Znak z najvišjo frekvenco je: d
str4: Makeuseof
Znak z najvišjo frekvenco je: e
str5: Ona vidi sir
Znak z najvišjo frekvenco je: e

Program JavaScript za iskanje znakov z najvišjo frekvenco

Spodaj je program JavaScript za iskanje znaka z najvišjo frekvenco v nizu:

// Program JavaScript za iskanje znaka
// z najvišjo frekvenco v nizu
naj bo ASCII_SIZE = 256;
funkcija maxFrequencyChar (str)
{
// Matrika za shranjevanje frekvence posameznih znakov
// Inicializirala je pogostost vsakega znaka kot 0
naj frekvenca = novo polje (ASCII_SIZE);
za (naj je i = 0; i {
frekvenca [i] = 0;
}
// Iskanje dolžine vhodnega niza
naj lenOfStr = str.length;
za (naj je i = 0; i {
frekvenca [str [i] .charCodeAt (0)] + = 1;
}
// Inicializiramo spremenljivko maxFrequency
naj maxFrequency = -1;
// Inicializiramo spremenljivko maxFrequencyChar
naj maxFrequencyChar = '';
// Prehod in vzdrževanje
// pogostost posameznih znakov
za (naj je i = 0; i {
if (maxFrequency {
maxFrequency = frekvenca [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
vrne maxFrequencyChar;
}
// Koda voznika
naj str1 = "Katera čarovnica je katera?";
document.write ("str1:" + str1 + "
");
document.write ("Znak z najvišjo frekvenco je:" + maxFrequencyChar (str1) + "
")
naj str2 = "Izvedel je tri proste mete";
document.write ("str2:" + str2 + "
");
document.write ("Znak z najvišjo frekvenco je:" + maxFrequencyChar (str2) + "
")
naj str3 = "Eddie jo je uredil";
document.write ("str3:" + str3 + "
");
document.write ("Znak z najvišjo frekvenco je:" + maxFrequencyChar (str3) + "
")
naj str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Znak z najvišjo frekvenco je:" + maxFrequencyChar (str4) + "
")
naj str5 = "Ona vidi sir";
document.write ("str5:" + str5 + "
");
document.write ("Znak z najvišjo frekvenco je:" + maxFrequencyChar (str5) + "
")

Izhod:

str1: Katera čarovnica je katera?
Znak z najvišjo frekvenco je: h
str2: Izvedel je tri proste mete
Znak z najvišjo frekvenco je: e
str3: Eddie ga je uredil
Znak z najvišjo frekvenco je: d
str4: Makeuseof
Znak z najvišjo frekvenco je: e
str5: Ona vidi sir
Znak z najvišjo frekvenco je: e

Analizirajte časovno in prostorsko kompleksnost

Časovna zapletenost maxFrequencyChar () funkcija je O (n). Prostorska zapletenost maxFrequencyChar () funkcija je O (1) kot fiksni presledek (matrika Hash). To ni odvisno od velikosti vhodnega niza.

Zapis Big-O vam omogoča, da izračunate, kako dolgo bo trajalo zagon vaše kode. To je eden najpomembnejših konceptov za analizo algoritmov. Če ste programer, morate vedeti o zapisu Big-O.

Yuvraj Chandra (30 objavljenih člankov)

Yuvraj je dodiplomski študent računalništva na Univerzi v Delhiju v Indiji. Navdušen je nad spletnim razvojem Full Stack. Ko ne piše, raziskuje globino različnih tehnologij.

Več od Yuvraj Chandra