Cum să găsiți cel mai frecvent personaj dintr-un șir

Corzile sunt un subiect foarte important în programarea interviurilor. Este înțelept să practici câteva probleme de programare axate pe șiruri înainte de interviuri. În acest articol, veți afla cum să găsiți cel mai frecvent personaj dintr-un șir.

Exemple pentru a înțelege problema

Exemplul 1: Lăsați șirul dat să fie „Makeuseof”. Caracterul „e” apare de 2 ori în șirul dat și toate celelalte caractere apar o singură dată. Astfel, caracterul „e” are cea mai mare frecvență în șirul dat.

Exemplul 2: Lasă șirul dat să fie „Ea vede brânză”. Caracterul „e” apare de 6 ori în șirul dat și toate celelalte caractere apar de mai puțin de 6 ori. Astfel, caracterul „e” are cea mai mare frecvență în șirul dat.

Abordare pentru a găsi cel mai frecvent personaj dintr-un șir

Tehnica de hash este cel mai eficient mod de a găsi personajul având cea mai mare frecvență într-un șir. În această tehnică, șirul este parcurs și fiecare caracter al șirului este hash într-o matrice de caractere ASCII.

Lăsați șirul de intrare să fie „Makeuseof”, fiecare caracter al acestui șir este hashed după cum urmează:

frecvență [„M”] = 1

frecvența ['a] = 1

frecvența ['k'] = 1

frecvența ['e'] = 2

frecvență ['u'] = 1

frecvența ['s'] = 1

frecvență ['o'] = 1

frecvență ['f'] = 1

Se returnează indexul valorii maxime din matricea de frecvență. Aici 2 este cea mai mare valoare, prin urmare se returnează „e”.

Program C ++ pentru a găsi caracterul cu cea mai mare frecvență

Mai jos este programul C ++ pentru a găsi caracterul cu cea mai mare frecvență într-un șir:

Legate de: Cum se numără aparițiile unui caracter dat într-un șir

// Program C ++ pentru a găsi caracterul
// având cea mai mare frecvență într-un șir
#include 
#include 
#define ASCII_SIZE 256
folosind spațiul de nume std;
char maxFrequencyChar (string str)
{
// Matrice pentru a stoca frecvența fiecărui personaj
// A inițializat frecvența fiecărui caracter ca 0
frecvența int [ASCII_SIZE] = {0};
// Găsirea lungimii șirului de intrare
int lenOfStr = str.length ();
// Inițializați variabila maxFrequency
int maxFrequency = -1;
// Inițializați variabila maxFrequencyChar
char maxFrequencyChar;
// Traversarea și menținerea
// frecvența fiecărui personaj
pentru (int i = 0; i {
frecvență [str [i]] ++;
if (frecvență maximă {
maxFrequency = frecvență [str [i]];
maxFrequencyChar = str [i];
}
}
returnează maxFrequencyChar;
}
// Cod șofer
int main ()
{
string str1 = "Care vrăjitoare este care?";
cout << "str1:" << str1 << endl;
cout << "Cel mai mare caracter de frecvență este:" << maxFrequencyChar (str1) << endl;
string str2 = "A aruncat trei aruncări libere";
cout << "str2:" << str2 << endl;
cout << "Cel mai mare caracter de frecvență este:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie l-a editat";
cout << "str3:" << str3 << endl;
cout << "Cel mai mare caracter de frecvență este:" << maxFrequencyChar (str3) << endl;
șir str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Cel mai mare caracter de frecvență este:" << maxFrequencyChar (str4) << endl;
string str5 = "Ea vede brânză";
cout << "str5:" << str5 << endl;
cout << "Cel mai mare caracter de frecvență este:" << maxFrequencyChar (str5) << endl;
}

Ieșire:

str1: Care vrăjitoare este care?
Cel mai mare caracter de frecvență este: h
str2: A aruncat trei aruncări libere
Cel mai mare caracter de frecvență este: e
str3: Eddie a editat-o
Cel mai mare caracter de frecvență este: d
str4: Makeuseof
Cel mai mare caracter de frecvență este: e
str5: Vede brânză
Cel mai mare caracter de frecvență este: e

Program Python pentru a găsi personajul cu cea mai mare frecvență

Mai jos este programul Python pentru a găsi caracterul cu cea mai mare frecvență într-un șir:

Legate de: Cum se inversează un șir în C ++, Python și JavaScript

# Program Python pentru a găsi personajul
# având cea mai mare frecvență într-un șir
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Matrice pentru a stoca frecvența fiecărui personaj
# A inițializat frecvența fiecărui caracter ca 0
frecvență = [0] * ASCII_SIZE
# Inițializați variabila maxFrequency
maxFrequency = -1
# Inițializați variabila maxFrequencyChar
maxFrequencyChar = "
# Trecerea și menținerea
# frecvența fiecărui personaj
pentru i în str:
frecvență [ord (i)] + = 1
pentru i în str:
dacă frecvență maximă maxFrequency = frecvență [ord (i)]
maxFrequencyChar = i
returnează maxFrequencyChar
# Cod șofer
str1 = "Care vrăjitoare este care?"
print ("str1:", str1)
print ("Cel mai mare caracter de frecvență este:", maxFrequencyChar (str1))
str2 = "A aruncat trei aruncări libere"
print ("str2:", str2)
print ("Cel mai mare caracter de frecvență este:", maxFrequencyChar (str2))
str3 = "Eddie a editat-o"
print ("str3:", str3)
print ("Cel mai mare caracter de frecvență este:", maxFrequencyChar (str3))
str4 = "Makeuseof"
print ("str4:", str4)
print ("Cel mai mare caracter de frecvență este:", maxFrequencyChar (str4))
str5 = "Ea vede brânză"
print ("str5:", str5)
print („Cel mai mare caracter de frecvență este:”, maxFrequencyChar (str5))

Ieșire:

str1: Care vrăjitoare este care?
Cel mai mare caracter de frecvență este: h
str2: A aruncat trei aruncări libere
Cel mai mare caracter de frecvență este: e
str3: Eddie a editat-o
Cel mai mare caracter de frecvență este: d
str4: Makeuseof
Cel mai mare caracter de frecvență este: e
str5: Vede brânză
Cel mai mare caracter de frecvență este: e

C Program pentru a găsi caracterul cu cea mai mare frecvență

Mai jos este programul C pentru a găsi caracterul cu cea mai mare frecvență într-un șir:

Legate de: Cum să găsiți vocale, consoane, cifre și caractere speciale într-un șir

// Program C pentru a găsi personajul
// având cea mai mare frecvență într-un șir
#include 
#include 
#define ASCII_SIZE 256
folosind spațiul de nume std;
char maxFrequencyChar (char * str)
{
// Matrice pentru a stoca frecvența fiecărui personaj
// A inițializat frecvența fiecărui caracter ca 0
frecvența int [ASCII_SIZE] = {0};
// Găsirea lungimii șirului de intrare
int lenOfStr = strlen (str);
// Inițializați variabila maxFrequency
int maxFrequency = 0;
// Inițializați variabila maxFrequencyChar
char maxFrequencyChar;
// Traversarea și menținerea
// frecvența fiecărui personaj
pentru (int i = 0; i {
frecvență [str [i]] ++;
if (frecvență maximă {
maxFrequency = frecvență [str [i]];
maxFrequencyChar = str [i];
}
}
returnează maxFrequencyChar;
}
// Cod șofer
int main ()
{
char str1 [] = "Care vrăjitoare este care?";
printf ("str1:% s", str1);
printf ("Cel mai mare caracter de frecvență este:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "A aruncat trei aruncări libere";
printf ("str2:% s", str2);
printf ("Cel mai mare caracter de frecvență este:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie a editat-o";
printf ("str3:% s", str3);
printf ("Cel mai mare caracter de frecvență este:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Cel mai mare caracter de frecvență este:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Ea vede brânză";
printf ("str1:% s", str5);
printf ("Cel mai mare caracter de frecvență este:% c \ ⁠n", maxFrequencyChar (str5));
}

Ieșire:

str1: Care vrăjitoare este care?
Cel mai mare caracter de frecvență este: h
str2: A aruncat trei aruncări libere
Cel mai mare caracter de frecvență este: e
str3: Eddie a editat-o
Cel mai mare caracter de frecvență este: d
str4: Makeuseof
Cel mai mare caracter de frecvență este: e
str5: Vede brânză
Cel mai mare caracter de frecvență este: e

Program JavaScript pentru a găsi caracterul cu cea mai mare frecvență

Mai jos este programul JavaScript pentru a găsi caracterul cu cea mai mare frecvență într-un șir:

// Program JavaScript pentru a găsi personajul
// având cea mai mare frecvență într-un șir
să ASCII_SIZE = 256;
function maxFrequencyChar (str)
{
// Matrice pentru a stoca frecvența fiecărui personaj
// A inițializat frecvența fiecărui caracter ca 0
Let Frequency = new Array (ASCII_SIZE);
pentru (să i = 0; i {
frecvența [i] = 0;
}
// Găsirea lungimii șirului de intrare
let lenOfStr = str.length;
pentru (să i = 0; i {
frecvență [str [i] .charCodeAt (0)] + = 1;
}
// Inițializați variabila maxFrequency
let maxFrequency = -1;
// Inițializați variabila maxFrequencyChar
let maxFrequencyChar = ";
// Traversarea și menținerea
// frecvența fiecărui personaj
pentru (să i = 0; i {
if (maxFrequency {
maxFrequency = frecvență [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
returnează maxFrequencyChar;
}
// Cod șofer
let str1 = "Care vrăjitoare este care?";
document.write ("str1:" + str1 + "
");
document.write ("Cel mai mare caracter de frecvență este:" + maxFrequencyChar (str1) + "
")
let str2 = "A aruncat trei aruncări libere";
document.write ("str2:" + str2 + "
");
document.write ("Cel mai mare caracter de frecvență este:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie a editat-o";
document.write ("str3:" + str3 + "
");
document.write ("Cel mai mare caracter de frecvență este:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Cel mai mare caracter de frecvență este:" + maxFrequencyChar (str4) + "
")
let str5 = "Ea vede brânză";
document.write ("str5:" + str5 + "
");
document.write ("Cel mai mare caracter de frecvență este:" + maxFrequencyChar (str5) + "
")

Ieșire:

str1: Care vrăjitoare este care?
Cel mai mare caracter de frecvență este: h
str2: A aruncat trei aruncări libere
Cel mai mare caracter de frecvență este: e
str3: Eddie a editat-o
Cel mai mare caracter de frecvență este: d
str4: Makeuseof
Cel mai mare caracter de frecvență este: e
str5: Vede brânză
Cel mai mare caracter de frecvență este: e

Analizați complexitatea timpului și spațiului

Complexitatea în timp a maxFrequencyChar () funcția este Pe). Complexitatea spațială a maxFrequencyChar () funcția este O (1) ca spațiu fix (matrice Hash). Nu depinde de dimensiunea șirului de intrare.

Notarea Big-O vă oferă o modalitate de a calcula cât timp va dura pentru a rula codul. Este unul dintre cele mai importante concepte pentru analiza algoritmilor. Dacă sunteți programator, trebuie să știți despre Big-O Notation.

Yuvraj Chandra (30 de articole publicate)

Yuvraj este student la Universitatea din Delhi, India. Este pasionat de dezvoltarea web Full Stack. Când nu scrie, explorează profunzimea diferitelor tehnologii.

Mai multe de la Yuvraj Chandra