Како пронаћи лик који се најчешће појављује у низу

Жице су веома важна тема у интервјуима за програмирање. Паметно је вежбати неке програмске проблеме усредсређене на жице пре интервјуа. У овом чланку ћете научити како пронаћи знак који се најчешће појављује у низу.

Примери за разумевање проблема

Пример 1: Нека дати низ буде "Макеусеоф". Знак 'е' се јавља два пута у датом низу, а сви остали знакови се јављају само једном. Дакле, знак 'е' има највећу фреквенцију у датом низу.

Пример 2: Нека дати низ буде „Она види сир“. Знак 'е' се јавља 6 пута у датом низу, а сви остали знакови се јављају мање од 6 пута. Дакле, знак 'е' има највећу фреквенцију у датом низу.

Приступ проналажењу лика који се најчешће појављује у низу

Техника хеширања је најефикаснији начин за проналажење лика са највећом фреквенцијом у низу. У овој техници се низ прелази и сваки знак низа хешира у низ АСЦИИ знакова.

Нека улазни низ буде "Макеусеоф", сваки знак овог низа је хеширан на следећи начин:

фреквенција ['М'] = 1

фреквенција ['а] = 1

фреквенција ['к'] = 1

фреквенција ['е'] = 2

фреквенција ['у'] = 1

фреквенција ['с'] = 1

фреквенција ['о'] = 1

фреквенција ['ф'] = 1

Враћен је индекс максималне вредности у фреквенцијском пољу. Ево 2 је највећа вредност, па се враћа 'е'.

Ц ++ програм за проналажење лика са највећом фреквенцијом

Испод је програм Ц ++ за проналажење знака са највећом фреквенцијом у низу:

Повезан: Како бројати појаве датог лика у низу

// Ц ++ програм за проналажење карактера
// са највећом фреквенцијом у низу
#инцлуде 
#инцлуде 
#дефине АСЦИИ_СИЗЕ 256
коришћење простора имена стд;
цхар макФрекуенциЦхар (стринг стр)
{
// Низ за чување фреквенције сваког знака
// Иницијализовао је учесталост сваког знака као 0
инт фреквенција [АСЦИИ_СИЗЕ] = {0};
// Проналажење дужине улазног низа
инт ленОфСтр = стр.ленгтх ();
// Иницијализација променљиве макФрекуенци
инт макФрекуенци = -1;
// Иницијализација променљиве макФрекуенциЦхар
цхар макФрекуенциЦхар;
// Прелазак и одржавање
// фреквенција сваког знака
за (инт и = 0; и {
фреквенција [стр [и]] ++;
иф (макФрекуенци {
макФрекуенци = фреквенција [стр [и]];
макФрекуенциЦхар = стр [и];
}
}
ретурн макФрекуенциЦхар;
}
// Код возача
инт маин ()
{
стринг стр1 = "Која је то вештица?";
цоут << "стр1:" << стр1 << ендл;
цоут << "Знак највише фреквенције је:" << макФрекуенциЦхар (стр1) << ендл;
стринг стр2 = "Бацио је три слободна бацања";
цоут << "стр2:" << стр2 << ендл;
цоут << "Знак највише фреквенције је:" << макФрекуенциЦхар (стр2) << ендл;
стринг стр3 = "Еддие га је уредио";
цоут << "стр3:" << стр3 << ендл;
цоут << "Знак највише фреквенције је:" << макФрекуенциЦхар (стр3) << ендл;
стринг стр4 = "Макеусеоф";
цоут << "стр4:" << стр4 << ендл;
цоут << "Знак највише фреквенције је:" << макФрекуенциЦхар (стр4) << ендл;
стринг стр5 = "Она види сир";
цоут << "стр5:" << стр5 << ендл;
цоут << "Знак највише фреквенције је:" << макФрекуенциЦхар (стр5) << ендл;
}

Излаз:

стр1: Која је вештица која?
Знак највише фреквенције је: х
стр2: Бацио је три слободна бацања
Знак највише фреквенције је: е
стр3: Еддие га је уредио
Знак највише фреквенције је: д
стр4: Макеусеоф
Знак највише фреквенције је: е
стр5: Она види сир
Знак највише фреквенције је: е

Питхон програм за проналажење лика са највећом фреквенцијом

Испод је програм Питхон за проналажење знака са највећом фреквенцијом у низу:

Повезан: Како обрнути низ у Ц ++, Питхон и ЈаваСцрипт

# Питхон програм за проналажење лика
# који имају највећу фреквенцију у низу
АСЦИИ_СИЗЕ = 256
деф макФрекуенциЦхар (стр):
# Низ за чување фреквенције сваког знака
# Иницијализовала је учесталост сваког знака као 0
фреквенција = [0] * АСЦИИ_СИЗЕ
# Иницијализујте променљиву макФрекуенци
макФрекуенци = -1
# Иницијализујте променљиву макФрекуенциЦхар
макФрекуенциЦхар = ''
# Прелазак и одржавање
# фреквенција сваког знака
за и у стр:
фреквенција [орд (и)] + = 1
за и у стр:
ако је макФрекуенци макФрекуенци = фреквенција [орд (и)]
макФрекуенциЦхар = и
ретурн макФрекуенциЦхар
# Код возача
стр1 = "Која је то вештица?"
испис ("стр1:", стр1)
принт ("Знак највише фреквенције је:", макФрекуенциЦхар (стр1))
стр2 = "Бацио је три слободна бацања"
испис ("стр2:", стр2)
принт ("Знак највише фреквенције је:", макФрекуенциЦхар (стр2))
стр3 = "Еддие га је уредио"
испис ("стр3:", стр3)
принт ("Знак највише фреквенције је:", макФрекуенциЦхар (стр3))
стр4 = "Макеусеоф"
испис ("стр4:", стр4)
принт ("Знак највише фреквенције је:", макФрекуенциЦхар (стр4))
стр5 = "Она види сир"
испис ("стр5:", стр5)
принт ("Знак највише фреквенције је:", макФрекуенциЦхар (стр5))

Излаз:

стр1: Која је вештица која?
Знак највише фреквенције је: х
стр2: Бацио је три слободна бацања
Знак највише фреквенције је: е
стр3: Еддие га је уредио
Знак највише фреквенције је: д
стр4: Макеусеоф
Знак највише фреквенције је: е
стр5: Она види сир
Знак највише фреквенције је: е

Ц програм за проналажење лика са највећом фреквенцијом

Испод је програм Ц за проналажење лика са највећом фреквенцијом у низу:

Повезан: Како пронаћи самогласнике, сугласнике, цифре и посебне знакове у низу

// Ц програм за проналажење лика
// са највећом фреквенцијом у низу
#инцлуде 
#инцлуде 
#дефине АСЦИИ_СИЗЕ 256
коришћење простора имена стд;
цхар макФрекуенциЦхар (цхар * стр)
{
// Низ за чување фреквенције сваког знака
// Иницијализовао је учесталост сваког знака као 0
инт фреквенција [АСЦИИ_СИЗЕ] = {0};
// Проналажење дужине улазног низа
инт ленОфСтр = стрлен (стр);
// Иницијализација променљиве макФрекуенци
инт макФрекуенци = 0;
// Иницијализација променљиве макФрекуенциЦхар
цхар макФрекуенциЦхар;
// Прелазак и одржавање
// фреквенција сваког знака
за (инт и = 0; и {
фреквенција [стр [и]] ++;
иф (макФрекуенци {
макФрекуенци = фреквенција [стр [и]];
макФрекуенциЦхар = стр [и];
}
}
ретурн макФрекуенциЦхар;
}
// Код возача
инт маин ()
{
цхар стр1 [] = "Која је то вештица?";
принтф ("стр1:% с", стр1);
принтф ("Знак највише фреквенције је:% ц \ ⁠н", макФрекуенциЦхар (стр1));
цхар стр2 [] = "Бацио је три слободна бацања";
принтф ("стр2:% с", стр2);
принтф ("Знак највише фреквенције је:% ц \ ⁠н", макФрекуенциЦхар (стр2));
цхар стр3 [] = "Еддие га је уредио";
принтф ("стр3:% с", стр3);
принтф ("Знак највише фреквенције је:% ц \ ⁠н", макФрекуенциЦхар (стр3));
цхар стр4 [] = "Макеусеоф";
принтф ("стр4:% с", стр4);
принтф ("Знак највише фреквенције је:% ц \ ⁠н", макФрекуенциЦхар (стр4));
цхар стр5 [] = "Она види сир";
принтф ("стр1:% с", стр5);
принтф ("Знак највише фреквенције је:% ц \ ⁠н", макФрекуенциЦхар (стр5));
}

Излаз:

стр1: Која је вештица која?
Знак највише фреквенције је: х
стр2: Бацио је три слободна бацања
Знак највише фреквенције је: е
стр3: Еддие га је уредио
Знак највише фреквенције је: д
стр4: Макеусеоф
Знак највише фреквенције је: е
стр5: Она види сир
Знак највише фреквенције је: е

ЈаваСцрипт програм за проналажење лика са највећом фреквенцијом

Испод је ЈаваСцрипт програм за проналажење знака са највећом фреквенцијом у низу:

// ЈаваСцрипт програм за проналажење карактера
// са највећом фреквенцијом у низу
нека АСЦИИ_СИЗЕ = 256;
функција макФрекуенциЦхар (стр)
{
// Низ за чување фреквенције сваког знака
// Иницијализовао је учесталост сваког знака као 0
нека фреквенција = нови низ (АСЦИИ_СИЗЕ);
за (нека је и = 0; и {
фреквенција [и] = 0;
}
// Проналажење дужине улазног низа
нека ленОфСтр = стр.ленгтх;
за (нека је и = 0; и {
фреквенција [стр [и] .цхарЦодеАт (0)] + = 1;
}
// Иницијализација променљиве макФрекуенци
нека је макФрекуенци = -1;
// Иницијализација променљиве макФрекуенциЦхар
нека макФрекуенциЦхар = '';
// Прелазак и одржавање
// фреквенција сваког знака
за (нека је и = 0; и {
иф (макФрекуенци {
макФрекуенци = фреквенција [стр [и] .цхарЦодеАт (0)];
макФрекуенциЦхар = стр [и];
}
}
ретурн макФрекуенциЦхар;
}
// Код возача
нека стр1 = "Која вештица је која?";
доцумент.врите ("стр1:" + стр1 + "
");
доцумент.врите ("Знак највише фреквенције је:" + макФрекуенциЦхар (стр1) + "
")
нека стр2 = "Бацио је три слободна бацања";
доцумент.врите ("стр2:" + стр2 + "
");
доцумент.врите ("Знак највише фреквенције је:" + макФрекуенциЦхар (стр2) + "
")
нека стр3 = "Еддие је то уредио";
доцумент.врите ("стр3:" + стр3 + "
");
доцумент.врите ("Знак са највећом фреквенцијом је:" + макФрекуенциЦхар (стр3) + "
")
нека стр4 = "Макеусеоф";
доцумент.врите ("стр4:" + стр4 + "
");
доцумент.врите ("Знак највише фреквенције је:" + макФрекуенциЦхар (стр4) + "
")
лет стр5 = "Она види сир";
доцумент.врите ("стр5:" + стр5 + "
");
доцумент.врите ("Знак највише фреквенције је:" + макФрекуенциЦхар (стр5) + "
")

Излаз:

стр1: Која је вештица која?
Знак највише фреквенције је: х
стр2: Бацио је три слободна бацања
Знак највише фреквенције је: е
стр3: Еддие га је уредио
Знак највише фреквенције је: д
стр4: Макеусеоф
Знак највише фреквенције је: е
стр5: Она види сир
Знак највише фреквенције је: е

Анализирајте временску и просторну сложеност

Временска сложеност макФрекуенциЦхар () функција је На). Сложеност простора макФрекуенциЦхар () функција је О (1) као фиксни размак (Хасх низ). Не зависи од величине улазног низа.

Ознака Биг-О вам даје начин да израчунате колико ће времена требати за покретање вашег кода. То је један од најважнијих концепата за анализу алгоритама. Ако сте програмер, морате знати о Биг-О нотацији.

Иуврај Цхандра (Објављено 30 чланака)

Иуврај је студент основних студија рачунарства на Универзитету у Делхију у Индији. Одушевљен је Фулл Стацк веб развојем. Када не пише, истражује дубину различитих технологија.

Још од Иуврај Цхандра