Het meest voorkomende karakter in een string vinden

Strings zijn een zeer belangrijk onderwerp bij het programmeren van interviews. Het is verstandig om voor je interviews wat programmeerproblemen te oefenen die gericht zijn op strings. In dit artikel leert u hoe u het meest voorkomende teken in een tekenreeks kunt vinden.

Voorbeelden om het probleem te begrijpen

voorbeeld 1: Laat de gegeven string "Makeuseof" zijn. Het teken 'e' komt 2 keer voor in de gegeven string en alle andere tekens komen slechts één keer voor. Het teken 'e' heeft dus de hoogste frequentie in de gegeven string.

Voorbeeld 2: Laat de gegeven string zijn "Ze ziet kaas". Het teken 'e' komt 6 keer voor in de gegeven string en alle andere tekens komen minder dan 6 keer voor. Het teken 'e' heeft dus de hoogste frequentie in de gegeven string.

Aanpak om het meest voorkomende karakter in een string te vinden

De hash-techniek is de meest efficiënte manier om het teken met de hoogste frequentie in een string te vinden. Bij deze techniek wordt de string doorlopen en wordt elk teken van de string gehasht in een array van ASCII-tekens.

Laat de invoerstring "Makeuseof" zijn, elk teken van deze string wordt als volgt gehasht:

frequentie['M'] = 1

frequentie['a] = 1

frequentie['k'] = 1

frequentie ['e'] = 2

frequentie['u'] = 1

frequentie['s'] = 1

frequentie['o'] = 1

frequentie['f'] = 1

De index van de maximale waarde in de frequentiereeks wordt geretourneerd. Hier 2 is de hoogste waarde, daarom wordt 'e' geretourneerd.

C++-programma om het personage met de hoogste frequentie te vinden

Hieronder staat het C++-programma om het teken met de hoogste frequentie in een string te vinden:

Verwant: Hoe het voorkomen van een bepaald karakter in een string te tellen?

// C++ programma om het karakter te vinden
// met de hoogste frequentie in een string
#include 
#include 
#define ASCII_SIZE 256
namespace std; gebruiken;
char maxFrequencyChar (string str)
{
// Array om de frequentie van elk karakter op te slaan
// Initialiseerde de frequentie van elk teken als 0
int frequentie [ASCII_SIZE] = {0};
// De lengte van de invoerstring vinden
int lenOfStr = str.lengte();
// Initialiseer maxFrequency variabele
int maxFrequentie = -1;
// Initialiseer maxFrequencyChar variabele
char maxFrequencyChar;
// Doorkruisen en onderhouden van de
// frequentie van elk karakter
voor (int i = 0; ik {
frequentie[str[i]]++;
if (maxFrequency < frequentie[str[i]])
{
maxFrequency = frequentie[str[i]];
maxFrequencyChar = str[i];
}
}
retourneer maxFrequencyChar;
}
// Bestuurderscode
int hoofd()
{
string str1 = "Welke heks is wat?";
cout << "str1: " << str1 << endl;
cout << "Het teken met de hoogste frequentie is: " << maxFrequencyChar (str1) << endl;
string str2 = "Hij gooide drie vrije worpen";
cout << "str2: " << str2 << endl;
cout << "Het teken met de hoogste frequentie is: " << maxFrequencyChar (str2) << endl;
string str3 = "Eddie heeft het aangepast";
cout << "str3: " << str3 << endl;
cout << "Het teken met de hoogste frequentie is: " << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4: " << str4 << endl;
cout << "Het teken met de hoogste frequentie is: " << maxFrequencyChar (str4) << endl;
string str5 = "Ze ziet kaas";
cout << "str5: " << str5 << endl;
cout << "Het teken met de hoogste frequentie is: " << maxFrequencyChar (str5) << endl;
}

Uitgang:

str1: Welke heks is welke?
Het teken met de hoogste frequentie is: h
str2: Hij gooide drie vrije worpen
Het teken met de hoogste frequentie is: e
str3: Eddie heeft het bewerkt
Het teken met de hoogste frequentie is: d
str4: Makeuseof
Het teken met de hoogste frequentie is: e
str5: Ze ziet kaas
Het teken met de hoogste frequentie is: e

Python-programma om het personage met de hoogste frequentie te vinden

Hieronder staat het Python-programma om het teken met de hoogste frequentie in een string te vinden:

Verwant: Een string omkeren in C++, Python en JavaScript

# Python-programma om het karakter te vinden
# met de hoogste frequentie in een string
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Array om de frequentie van elk karakter op te slaan
# Initialiseerde de frequentie van elk teken als 0
frequentie = [0] * ASCII_SIZE
# Initialiseer maxFrequency variabele
maxFrequentie = -1
# Initialiseer maxFrequencyChar variabele
maxFrequencyChar = ''
# Doorkruisen en onderhouden van de
# frequentie van elk karakter
voor ik in str:
frequentie[ord (i)] += 1
voor ik in str:
als maxFrequency < frequentie[ord (i)]:
maxFrequency = frequentie [ord (i)]
maxFrequencyChar = i
retour maxFrequencyChar
# Bestuurderscode
str1 = "Welke heks is welke?"
print("str1:", str1)
print("Het teken met de hoogste frequentie is:", maxFrequencyChar (str1))
str2 = "Hij gooide drie vrije worpen"
print("str2:", str2)
print("Het teken met de hoogste frequentie is:", maxFrequencyChar (str2))
str3 = "Eddie heeft het bewerkt"
print("str3:", str3)
print("Het teken met de hoogste frequentie is:", maxFrequencyChar (str3))
str4 = "Maak gebruik van"
print("str4:", str4)
print("Het teken met de hoogste frequentie is:", maxFrequencyChar (str4))
str5 = "Ze ziet kaas"
print("str5:", str5)
print("Het teken met de hoogste frequentie is:", maxFrequencyChar (str5))

Uitgang:

str1: Welke heks is welke?
Het teken met de hoogste frequentie is: h
str2: Hij gooide drie vrije worpen
Het teken met de hoogste frequentie is: e
str3: Eddie heeft het bewerkt
Het teken met de hoogste frequentie is: d
str4: Makeuseof
Het teken met de hoogste frequentie is: e
str5: Ze ziet kaas
Het teken met de hoogste frequentie is: e

C Programma om het personage met de hoogste frequentie te vinden

Hieronder staat het C-programma om het teken met de hoogste frequentie in een string te vinden:

Verwant: Klinkers, medeklinkers, cijfers en speciale tekens in een string vinden

// C-programma om het personage te vinden
// met de hoogste frequentie in een string
#include 
#include 
#define ASCII_SIZE 256
namespace std; gebruiken;
char maxFrequencyChar (char *str)
{
// Array om de frequentie van elk karakter op te slaan
// Initialiseerde de frequentie van elk teken als 0
int frequentie [ASCII_SIZE] = {0};
// De lengte van de invoerstring vinden
int lenOfStr = strlen (str);
// Initialiseer maxFrequency variabele
int maxFrequentie = 0;
// Initialiseer maxFrequencyChar variabele
char maxFrequencyChar;
// Doorkruisen en onderhouden van de
// frequentie van elk karakter
voor (int i = 0; ik {
frequentie[str[i]]++;
if (maxFrequency < frequentie[str[i]])
{
maxFrequency = frequentie[str[i]];
maxFrequencyChar = str[i];
}
}
retourneer maxFrequencyChar;
}
// Bestuurderscode
int hoofd()
{
char str1[] = "Welke heks is welke?";
printf("str1: %s", str1);
printf("Het teken met de hoogste frequentie is: %c \⁠n", maxFrequencyChar (str1));
char str2[] ​​= "Hij gooide drie vrije worpen";
printf("str2: %s", str2);
printf("Het teken met de hoogste frequentie is: %c \⁠n", maxFrequencyChar (str2));
char str3[] = "Eddie heeft het aangepast";
printf("str3: %s", str3);
printf("Het teken met de hoogste frequentie is: %c \⁠n", maxFrequencyChar (str3));
char str4[] = "Makeuseof";
printf("str4: %s", str4);
printf("Het teken met de hoogste frequentie is: %c \⁠n", maxFrequencyChar (str4));
char str5[] = "Ze ziet kaas";
printf("str1: %s", str5);
printf("Het teken met de hoogste frequentie is: %c \⁠n", maxFrequencyChar (str5));
}

Uitgang:

str1: Welke heks is welke?
Het teken met de hoogste frequentie is: h
str2: Hij gooide drie vrije worpen
Het teken met de hoogste frequentie is: e
str3: Eddie heeft het bewerkt
Het teken met de hoogste frequentie is: d
str4: Makeuseof
Het teken met de hoogste frequentie is: e
str5: Ze ziet kaas
Het teken met de hoogste frequentie is: e

JavaScript-programma om het personage met de hoogste frequentie te vinden

Hieronder staat het JavaScript-programma om het teken met de hoogste frequentie in een string te vinden:

// JavaScript-programma om het teken te vinden
// met de hoogste frequentie in een string
laat ASCII_SIZE = 256;
functie maxFrequencyChar (str)
{
// Array om de frequentie van elk karakter op te slaan
// Initialiseerde de frequentie van elk teken als 0
laat frequentie = nieuwe array (ASCII_SIZE);
voor (laat ik = 0; ik < ASCII_SIZE; ik++)
{
frequentie[i] = 0;
}
// De lengte van de invoerstring vinden
laat lenOfStr = str.lengte;
voor (laat ik = 0; ik {
frequentie[str[i].charCodeAt (0)] += 1;
}
// Initialiseer maxFrequency variabele
laat maxFrequency = -1;
// Initialiseer maxFrequencyChar variabele
laat maxFrequencyChar = '';
// Doorkruisen en onderhouden van de
// frequentie van elk karakter
voor (laat ik = 0; ik {
if (maxFrequency < frequentie[str[i].charCodeAt (0)])
{
maxFrequency = frequentie[str[i].charCodeAt (0)];
maxFrequencyChar = str[i];
}
}
retourneer maxFrequencyChar;
}
// Bestuurderscode
let str1 = "Welke heks is wat?";
document.write("str1: " + str1 + "
");
document.write("Het teken met de hoogste frequentie is: " + maxFrequencyChar (str1) + "
")
let str2 = "Hij gooide drie vrije worpen";
document.write("str2: " + str2 + "
");
document.write("Het teken met de hoogste frequentie is: " + maxFrequencyChar (str2) + "
")
let str3 = "Eddie heeft het aangepast";
document.write("str3: " + str3 + "
");
document.write("Het teken met de hoogste frequentie is: " + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write("str4: " + str4 + "
");
document.write("Het teken met de hoogste frequentie is: " + maxFrequencyChar (str4) + "
")
let str5 = "Ze ziet kaas";
document.write("str5: " + str5 + "
");
document.write("Het teken met de hoogste frequentie is: " + maxFrequencyChar (str5) + "
")

Uitgang:

str1: Welke heks is welke?
Het teken met de hoogste frequentie is: h
str2: Hij gooide drie vrije worpen
Het teken met de hoogste frequentie is: e
str3: Eddie heeft het bewerkt
Het teken met de hoogste frequentie is: d
str4: Makeuseof
Het teken met de hoogste frequentie is: e
str5: Ze ziet kaas
Het teken met de hoogste frequentie is: e

Analyseer de tijd- en ruimtecomplexiteit

De tijdscomplexiteit van de maxFrequencyChar() functie is Aan). De ruimtecomplexiteit van de maxFrequencyChar() functie is O(1) als een vaste spatie (Hash-array). Het is niet afhankelijk van de grootte van de invoerreeks.

Big-O-notatie geeft u een manier om te berekenen hoe lang het duurt om uw code uit te voeren. Het is een van de belangrijkste concepten voor de analyse van algoritmen. Als je een programmeur bent, moet je kennis hebben van Big-O Notation.

Yuvraj Chandra (30 artikelen gepubliceerd)

Yuvraj is een student Computerwetenschappen aan de Universiteit van Delhi, India. Hij is gepassioneerd door Full Stack Web Development. Als hij niet aan het schrijven is, onderzoekt hij de diepte van verschillende technologieën.

Meer van Yuvraj Chandra