Kuinka löytää merkkijonossa useimmin esiintyvä merkki

Jouset ovat erittäin tärkeä aihe haastattelujen ohjelmoinnissa. On järkevää harjoitella joitain ohjelmointiongelmia, jotka keskittyvät jousiin ennen haastatteluja. Tässä artikkelissa opit etsimään merkkijonossa yleisimmin esiintyvän merkin.

Esimerkkejä ongelman ymmärtämiseksi

Esimerkki 1: Olkoon annettu merkkijono "Makeuseof". Merkki 'e' esiintyy 2 kertaa annetussa merkkijonossa ja kaikki muut merkit esiintyvät vain kerran. Täten merkillä 'e' on korkein taajuus annetussa merkkijonossa.

Esimerkki 2: Olkoon annettu merkkijono "Hän näkee juustoa". Merkki 'e' esiintyy 6 kertaa annetussa merkkijonossa ja kaikki muut merkit esiintyvät alle 6 kertaa. Täten merkillä 'e' on korkein taajuus annetussa merkkijonossa.

Lähestymistapa merkkijonon useimmin esiintyvän hahmon löytämiseen

Hajautustekniikka on tehokkain tapa löytää merkki, jolla on korkein taajuus merkkijonossa. Tässä tekniikassa merkkijono kulkee läpi ja jokainen merkkijono hajautetaan ASCII-merkkien joukkoon.

Olkoon syötemerkkijono "Makeuseof", jokainen merkkijono hajautetaan seuraavasti:

taajuus ['M'] = 1

taajuus ['a] = 1

taajuus ['k'] = 1

taajuus ['e'] = 2

taajuus ['u'] = 1

taajuus ['s'] = 1

taajuus ['o'] = 1

taajuus ['f'] = 1

Palautetaan taajuusryhmän maksimiarvon indeksi. Tässä 2 on korkein arvo, siksi 'e' palautetaan.

C ++ -ohjelma korkeimman taajuuden omaavan merkin löytämiseksi

Alla on C ++ -ohjelma merkin korkeimman taajuuden löytämiseksi:

Liittyvät: Kuinka laskea merkkijonossa esiintyvän merkin esiintymät

// C ++ -ohjelma merkin löytämiseksi
// jolla on korkein merkkijono merkkijonossa
#sisältää 
#sisältää 
#define ASCII_SIZE 256
käyttämällä nimitilaa vakio;
char maxFrequencyChar (merkkijono str)
{
// Taulukko kunkin merkin taajuuden tallentamiseksi
// Alustettiin kunkin merkin taajuudeksi 0
int-taajuus [ASCII_SIZE] = {0};
// Syötetään merkkijonon pituus
int lenOfStr = str.pituus ();
// Alusta maxFrequency-muuttuja
int maxTaajuus = -1;
// Alusta maxFrequencyChar-muuttuja
char maxFrequencyChar;
// Liikkuminen ja ylläpito
// kunkin merkin taajuus
for (int i = 0; i {
taajuus [str [i]] ++;
jos (maxTaajuus {
maxFrequency = taajuus [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Kuljettajan koodi
int main ()
{
string str1 = "Mikä noita on mikä?";
cout << "str1:" << str1 << endl;
cout << "Korkein taajuusmerkki on:" << maxFrequencyChar (str1) << endl;
string str2 = "Hän heitti kolme vapaaheittoa";
cout << "str2:" << str2 << endl;
cout << "Korkein taajuusmerkki on:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie muokkasi sitä";
cout << "str3:" << str3 << endl;
cout << "Korkein taajuusmerkki on:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Korkein taajuusmerkki on:" << maxFrequencyChar (str4) << endl;
string str5 = "Hän näkee juustoa";
cout << "str5:" << str5 << endl;
cout << "Korkein taajuusmerkki on:" << maxFrequencyChar (str5) << endl;
}

Tuotos:

str1: Mikä noita on mikä?
Korkein taajuusmerkki on: h
str2: Hän heitti kolme vapaaheittoa
Korkein taajuusmerkki on: e
str3: Eddie muokkasi sitä
Korkein taajuusmerkki on: d
str4: Käyttö
Korkein taajuusmerkki on: e
str5: Hän näkee juustoa
Korkein taajuusmerkki on: e

Python-ohjelma korkeimman taajuuden omaavan merkin löytämiseksi

Alla on Python-ohjelma merkkijonon korkeimman taajuuden löytämiseksi:

Liittyvät: Merkkijonon kääntäminen C ++: ssa, Pythonissa ja JavaScriptissä

# Python-ohjelma merkin löytämiseksi
# jolla on korkein merkkijono merkkijonossa
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Taulukko kunkin merkin taajuuden tallentamiseksi
# Alustettiin kunkin merkin taajuudeksi 0
taajuus = [0] * ASCII_SIZE
# Alusta maxFrequency-muuttuja
maxTaajuus = -1
# Alusta maxFrequencyChar-muuttuja
maxFrequencyChar = ''
# Liikkuminen ja ylläpito
# kunkin merkin taajuus
i: lle str: ssä:
taajuus [ord (i)] + = 1
i: lle str: ssä:
jos maxFrequency maxFrequency = taajuus [ord (i)]
maxFrequencyChar = i
return maxFrequencyChar
# Kuljettajan koodi
str1 = "Mikä noita on mikä?"
tulosta ("str1:", str1)
tulosta ("Korkein taajuusmerkki on:", maxFrequencyChar (str1))
str2 = "Hän heitti kolme vapaaheittoa"
tulosta ("str2:", str2)
tulosta ("Korkein taajuusmerkki on:", maxFrequencyChar (str2))
str3 = "Eddie muokkasi sitä"
tulosta ("str3:", str3)
tulosta ("Korkein taajuusmerkki on:", maxFrequencyChar (str3))
str4 = "Makeuseof"
tulosta ("str4:", str4)
tulosta ("Korkein taajuusmerkki on:", maxFrequencyChar (str4))
str5 = "Hän näkee juustoa"
tulosta ("str5:", str5)
tulosta ("Korkein taajuusmerkki on:", maxFrequencyChar (str5))

Tuotos:

str1: Mikä noita on mikä?
Korkein taajuusmerkki on: h
str2: Hän heitti kolme vapaaheittoa
Korkein taajuusmerkki on: e
str3: Eddie muokkasi sitä
Korkein taajuusmerkki on: d
str4: Käyttö
Korkein taajuusmerkki on: e
str5: Hän näkee juustoa
Korkein taajuusmerkki on: e

C Ohjelma suurimman taajuuden omaavan merkin löytämiseksi

Alla on C-ohjelma merkin korkeimman taajuuden löytämiseksi:

Liittyvät: Kuinka löytää vokaaleja, konsonantteja, numeroita ja erikoismerkkejä merkkijonosta

// C-ohjelma merkin löytämiseksi
// jolla on korkein merkkijono merkkijonossa
#sisältää 
#sisältää 
#define ASCII_SIZE 256
käyttämällä nimitilaa vakio;
char maxFrequencyChar (char * str)
{
// Taulukko kunkin merkin taajuuden tallentamiseksi
// Alustettiin kunkin merkin taajuudeksi 0
int-taajuus [ASCII_SIZE] = {0};
// Syötetään merkkijonon pituus
int lenOfStr = strlen (str);
// Alusta maxFrequency-muuttuja
int maxTaajuus = 0;
// Alusta maxFrequencyChar-muuttuja
char maxFrequencyChar;
// Liikkuminen ja ylläpito
// kunkin merkin taajuus
for (int i = 0; i {
taajuus [str [i]] ++;
jos (maxTaajuus {
maxFrequency = taajuus [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Kuljettajan koodi
int main ()
{
char str1 [] = "Mikä noita on mikä?";
printf ("str1:% s", str1);
printf ("Korkein taajuusmerkki on:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Hän heitti kolme vapaaheittoa";
printf ("str2:% s", str2);
printf ("Korkein taajuusmerkki on:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie muokkasi sitä";
printf ("str3:% s", str3);
printf ("Korkein taajuusmerkki on:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Korkein taajuusmerkki on:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Hän näkee juustoa";
printf ("str1:% s", str5);
printf ("Korkein taajuusmerkki on:% c \ ⁠n", maxFrequencyChar (str5));
}

Tuotos:

str1: Mikä noita on mikä?
Korkein taajuusmerkki on: h
str2: Hän heitti kolme vapaaheittoa
Korkein taajuusmerkki on: e
str3: Eddie muokkasi sitä
Korkein taajuusmerkki on: d
str4: Käyttö
Korkein taajuusmerkki on: e
str5: Hän näkee juustoa
Korkein taajuusmerkki on: e

JavaScript-ohjelma korkeimman taajuuden omaavan merkin löytämiseksi

Alla on JavaScript-ohjelma merkin korkeimman taajuuden löytämiseksi:

// JavaScript-ohjelma merkin löytämiseksi
// jolla on korkein merkkijono merkkijonossa
olkoon ASCII_SIZE = 256;
funktio maxFrequencyChar (str)
{
// Taulukko kunkin merkin taajuuden tallentamiseksi
// Alustettiin kunkin merkin taajuudeksi 0
anna taajuus = uusi taulukko (ASCII_SIZE);
for (olkoon i = 0; i {
taajuus [i] = 0;
}
// Syötetään merkkijonon pituus
olkoon lenOfStr = str.pituus;
for (olkoon i = 0; i {
taajuus [str [i] .charCodeAt (0)] + = 1;
}
// Alusta maxFrequency-muuttuja
olkoon maxFrequency = -1;
// Alusta maxFrequencyChar-muuttuja
anna maxFrequencyChar = '';
// Liikkuminen ja ylläpito
// kunkin merkin taajuus
for (olkoon i = 0; i {
jos (maxFrequency {
maxFrequency = taajuus [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Kuljettajan koodi
anna str1 = "Mikä noita on mikä?";
document.write ("str1:" + str1 + "
");
document.write ("Korkein taajuusmerkki on:" + maxFrequencyChar (str1) + "
")
anna str2 = "Hän heitti kolme vapaaheittoa";
document.write ("str2:" + str2 + "
");
document.write ("Korkein taajuusmerkki on:" + maxFrequencyChar (str2) + "
")
anna str3 = "Eddie muokkasi sitä";
document.write ("str3:" + str3 + "
");
document.write ("Korkein taajuusmerkki on:" + maxFrequencyChar (str3) + "
")
anna str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Korkein taajuusmerkki on:" + maxFrequencyChar (str4) + "
")
let str5 = "Hän näkee juustoa";
document.write ("str5:" + str5 + "
");
document.write ("Korkein taajuusmerkki on:" + maxFrequencyChar (str5) + "
")

Tuotos:

str1: Mikä noita on mikä?
Korkein taajuusmerkki on: h
str2: Hän heitti kolme vapaaheittoa
Korkein taajuusmerkki on: e
str3: Eddie muokkasi sitä
Korkein taajuusmerkki on: d
str4: Käyttö
Korkein taajuusmerkki on: e
str5: Hän näkee juustoa
Korkein taajuusmerkki on: e

Analysoi ajan ja avaruuden monimutkaisuus

Ajan monimutkaisuus maxFrequencyChar () toiminto on Päällä). Avaruuden monimutkaisuus maxFrequencyChar () toiminto on O (1) kiinteänä tilana (Hash-taulukko). Se ei riipu syötetyn merkkijonon koosta.

Big-O-notaatio antaa sinulle tavan laskea kuinka kauan kestää koodisi suorittaminen. Se on yksi tärkeimmistä käsitteistä algoritmien analysoimiseksi. Jos olet ohjelmoija, sinun on tiedettävä Big-O-merkinnästä.

Yuvraj Chandra (30 artikkelia julkaistu)

Yuvraj on tietojenkäsittelytieteen perustutkinto-opiskelija Delhin yliopistossa Intiassa. Hän on intohimoisesti Full Stack -verkkokehitys. Kun hän ei kirjoita, hän tutkii eri tekniikoiden syvyyttä.

Lisää artistilta Yuvraj Chandra