Kako pronaći lik koji se najčešće pojavljuje u nizu

Žice su vrlo važna tema u programskim intervjuima. Pametno je prije intervjua uvježbati neke programske probleme usredotočene na žice. U ovom ćete članku naučiti kako pronaći znak koji se najčešće pojavljuje u nizu.

Primjeri za razumijevanje problema

Primjer 1: Neka zadani niz bude "Makeuseof". Znak 'e' pojavljuje se 2 puta u zadanom nizu, a svi ostali znakovi pojavljuju se samo jednom. Dakle, znak 'e' ima najveću frekvenciju u zadanom nizu.

Primjer 2: Neka zadani niz bude "Ona vidi sir". Znak 'e' pojavljuje se 6 puta u zadanom nizu, a svi ostali znakovi pojavljuju se manje od 6 puta. Dakle, znak 'e' ima najveću frekvenciju u zadanom nizu.

Pristup pronalaženju lika koji se najčešće pojavljuje u nizu

Tehnika raspršivanja najučinkovitiji je način pronalaska lika s najvećom frekvencijom u nizu. U ovoj se tehnici niz prelazi i svaki znak niza raspršuje u niz ASCII znakova.

Neka ulazni niz bude "Makeuseof", svaki znak ovog niza heširan je na sljedeći način:

frekvencija ['M'] = 1

frekvencija ['a] = 1

frekvencija ['k'] = 1

frekvencija ['e'] = 2

frekvencija ['u'] = 1

frekvencija ['s'] = 1

frekvencija ['o'] = 1

frekvencija ['f'] = 1

Vraćen je indeks maksimalne vrijednosti u frekvencijskom polju. Ovdje 2 je najviša vrijednost, pa se vraća 'e'.

C ++ program za pronalaženje lika s najvećom frekvencijom

Ispod je program C ++ za pronalaženje znaka s najvećom frekvencijom u nizu:

Povezano: Kako brojati pojave datog lika u nizu

// C ++ program za pronalaženje lika
// s najvećom frekvencijom u nizu
#include 
#include 
#define ASCII_SIZE 256
pomoću prostora imena std;
char maxFrequencyChar (niz str)
{
// Niz za pohranu frekvencije svakog znaka
// Inicijalizirala je učestalost svakog znaka kao 0
int frekvencija [ASCII_SIZE] = {0};
// Pronalaženje duljine ulaznog niza
int lenOfStr = str.length ();
// Inicijalizacija varijable maxFrequency
int maxFrequency = -1;
// Inicijalizirajte varijablu maxFrequencyChar
char maxFrequencyChar;
// Prelazak i održavanje
// frekvencija svakog znaka
za (int i = 0; i {
frekvencija [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvencija [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Šifra vozača
int main ()
{
string str1 = "Koja je vještica koja?";
cout << "str1:" << str1 << endl;
cout << "Znak najviše frekvencije je:" << maxFrequencyChar (str1) << endl;
string str2 = "Bacio je tri slobodna bacanja";
cout << "str2:" << str2 << endl;
cout << "Znak najveće frekvencije je:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie je to uredio";
cout << "str3:" << str3 << endl;
cout << "Znak najviše frekvencije je:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Znak najviše frekvencije je:" << maxFrequencyChar (str4) << endl;
string str5 = "Ona vidi sir";
cout << "str5:" << str5 << endl;
cout << "Znak najviše frekvencije je:" << maxFrequencyChar (str5) << endl;
}

Izlaz:

str1: Koja je vještica koja?
Znak najviše frekvencije je: h
str2: Bacio je tri slobodna bacanja
Znak najviše frekvencije je: e
str3: Eddie ga je uredio
Znak najviše frekvencije je: d
str4: Makeuseof
Znak najviše frekvencije je: e
str5: Ona vidi sir
Znak najviše frekvencije je: e

Python program za pronalaženje lika s najvećom frekvencijom

Ispod je program Python za pronalaženje znaka s najvećom frekvencijom u nizu:

Povezano: Kako obrnuti niz u C ++, Python i JavaScript

# Python program za pronalaženje lika
# s najvećom frekvencijom u nizu
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Niz za pohranu učestalosti pojedinih znakova
# Inicijalizirala je učestalost svakog znaka kao 0
frekvencija = [0] * ASCII_SIZE
# Inicijalizirajte varijablu maxFrequency
maxFrequency = -1
# Inicijalizirajte varijablu maxFrequencyChar
maxFrequencyChar = ''
# Prelazak i održavanje
# frekvencija svakog znaka
za ja u str:
frekvencija [ord (i)] + = 1
za ja u str:
ako je maxFrequency maxFrequency = frekvencija [ord (i)]
maxFrequencyChar = i
vrati maxFrequencyChar
# Šifra vozača
str1 = "Koja je vještica koja?"
ispis ("str1:", str1)
print ("Znak najviše frekvencije je:", maxFrequencyChar (str1))
str2 = "Bacio je tri slobodna bacanja"
ispis ("str2:", str2)
print ("Znak najviše frekvencije je:", maxFrequencyChar (str2))
str3 = "Eddie je to uredio"
ispis ("str3:", str3)
print ("Znak najviše frekvencije je:", maxFrequencyChar (str3))
str4 = "Makeuseof"
ispis ("str4:", str4)
print ("Znak najviše frekvencije je:", maxFrequencyChar (str4))
str5 = "Ona vidi sir"
ispis ("str5:", str5)
print ("Znak najviše frekvencije je:", maxFrequencyChar (str5))

Izlaz:

str1: Koja je vještica koja?
Znak najviše frekvencije je: h
str2: Bacio je tri slobodna bacanja
Znak najviše frekvencije je: e
str3: Eddie ga je uredio
Znak najviše frekvencije je: d
str4: Makeuseof
Znak najviše frekvencije je: e
str5: Ona vidi sir
Znak najviše frekvencije je: e

C program za pronalaženje lika s najvećom frekvencijom

Ispod je program C za pronalaženje znaka s najvećom frekvencijom u nizu:

Povezano: Kako pronaći samoglasnike, suglasnike, znamenke i posebne znakove u nizu

// C program za pronalaženje lika
// s najvećom frekvencijom u nizu
#include 
#include 
#define ASCII_SIZE 256
pomoću prostora imena std;
char maxFrequencyChar (char * str)
{
// Niz za pohranu frekvencije svakog znaka
// Inicijalizirala je učestalost svakog znaka kao 0
int frekvencija [ASCII_SIZE] = {0};
// Pronalaženje duljine ulaznog niza
int lenOfStr = strlen (str);
// Inicijalizacija varijable maxFrequency
int maxFrequency = 0;
// Inicijalizirajte varijablu maxFrequencyChar
char maxFrequencyChar;
// Prelazak i održavanje
// frekvencija svakog znaka
za (int i = 0; i {
frekvencija [str [i]] ++;
if (maxFrequency {
maxFrequency = frekvencija [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Šifra vozača
int main ()
{
char str1 [] = "Koja je vještica?";
printf ("str1:% s", str1);
printf ("Znak najviše frekvencije je:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Bacio je tri slobodna bacanja";
printf ("str2:% s", str2);
printf ("Znak najviše frekvencije je:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie je to uredio";
printf ("str3:% s", str3);
printf ("Znak najviše frekvencije je:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Znak najveće frekvencije je:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Ona vidi sir";
printf ("str1:% s", str5);
printf ("Znak najviše frekvencije je:% c \ ⁠n", maxFrequencyChar (str5));
}

Izlaz:

str1: Koja je vještica koja?
Znak najviše frekvencije je: h
str2: Bacio je tri slobodna bacanja
Znak najviše frekvencije je: e
str3: Eddie ga je uredio
Znak najviše frekvencije je: d
str4: Makeuseof
Znak najviše frekvencije je: e
str5: Ona vidi sir
Znak najviše frekvencije je: e

JavaScript program za pronalaženje lika s najvećom frekvencijom

Ispod je JavaScript program za pronalaženje znaka s najvećom frekvencijom u nizu:

// JavaScript program za pronalaženje lika
// s najvećom frekvencijom u nizu
neka ASCII_SIZE = 256;
funkcija maxFrequencyChar (str)
{
// Niz za pohranu frekvencije svakog znaka
// Inicijalizirala je učestalost svakog znaka kao 0
neka frekvencija = novi niz (ASCII_SIZE);
za (neka je i = 0; i {
frekvencija [i] = 0;
}
// Pronalaženje duljine ulaznog niza
neka lenOfStr = str.length;
za (neka je i = 0; i {
frekvencija [str [i] .charCodeAt (0)] + = 1;
}
// Inicijalizacija varijable maxFrequency
neka je maxFrequency = -1;
// Inicijalizirajte varijablu maxFrequencyChar
neka maxFrequencyChar = '';
// Prelazak i održavanje
// frekvencija svakog znaka
za (neka je i = 0; i {
if (maxFrequency {
maxFrequency = frekvencija [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Šifra vozača
neka str1 = "Koja je vještica koja?";
document.write ("str1:" + str1 + "
");
document.write ("Znak najviše frekvencije je:" + maxFrequencyChar (str1) + "
")
neka str2 = "Bacio je tri slobodna bacanja";
document.write ("str2:" + str2 + "
");
document.write ("Znak najviše frekvencije je:" + maxFrequencyChar (str2) + "
")
neka str3 = "Eddie je to uredio";
document.write ("str3:" + str3 + "
");
document.write ("Znak najviše frekvencije je:" + maxFrequencyChar (str3) + "
")
neka str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Znak najviše frekvencije je:" + maxFrequencyChar (str4) + "
")
neka str5 = "Ona vidi sir";
document.write ("str5:" + str5 + "
");
document.write ("Znak najviše frekvencije je:" + maxFrequencyChar (str5) + "
")

Izlaz:

str1: Koja je vještica koja?
Znak najviše frekvencije je: h
str2: Bacio je tri slobodna bacanja
Znak najviše frekvencije je: e
str3: Eddie ga je uredio
Znak najviše frekvencije je: d
str4: Makeuseof
Znak najviše frekvencije je: e
str5: Ona vidi sir
Znak najviše frekvencije je: e

Analizirajte vremensku i prostornu složenost

Vremenska složenost maxFrequencyChar () funkcija je Na). Složenost prostora maxFrequencyChar () funkcija je O (1) kao fiksni prostor (Hash niz). Ne ovisi o veličini ulaznog niza.

Oznaka Big-O daje vam način izračuna koliko će vremena trebati za pokretanje vašeg koda. To je jedan od najvažnijih koncepata za analizu algoritama. Ako ste programer, morate znati o Big-O notaciji.

Yuvraj Chandra (Objavljeno 30 članaka)

Yuvraj je studentica preddiplomskog studija računarstva na Sveučilištu u Delhiju u Indiji. Zaljubljen je u Full Stack web razvoj. Kad ne piše, istražuje dubinu različitih tehnologija.

Više od Yuvraja Chandre