כיצד למצוא את הדמות הנפוצה ביותר במחרוזת

מיתרים הם נושא חשוב מאוד בראיונות תכנות. זה חכם לתרגל כמה בעיות תכנות הממוקדות במיתרים לפני הראיונות שלך. במאמר זה תלמד כיצד למצוא את הדמות הנפוצה ביותר במחרוזת.

דוגמאות להבנת הבעיה

דוגמה 1: תנו למחרוזת הנתונה להיות "Makeuseof". הדמות 'e' מופיעה פעמיים במחרוזת הנתונה וכל שאר הדמויות מתרחשות רק פעם אחת. לפיכך, הדמות 'e' כוללת את התדירות הגבוהה ביותר במחרוזת הנתונה.

דוגמה 2: תנו למחרוזת הנתונה להיות "היא רואה גבינה". הדמות 'e' מופיעה 6 פעמים במחרוזת הנתונה וכל שאר התווים מופיעים פחות מ 6 פעמים. לפיכך, הדמות 'e' כוללת את התדירות הגבוהה ביותר במחרוזת הנתונה.

גישה למצוא את הדמות הנפוצה ביותר במחרוזת

טכניקת הגיבוב היא הדרך היעילה ביותר למצוא את הדמות בעלת התדירות הגבוהה ביותר במחרוזת. בטכניקה זו מעבירים את המחרוזת וכל תו של המחרוזת מגולף למערך של תווי ASCII.

תנו למחרוזת הקלט להיות "Makeuseof", כל תו של מחרוזת זו נחפף כדלקמן:

תדר ['M'] = 1

תדר ['a] = 1

תדר ['k'] = 1

תדר ['e'] = 2

תדר ['u'] = 1

תדר ['s'] = 1

תדר ['o'] = 1

תדר ['f'] = 1

אינדקס הערך המרבי במערך התדרים מוחזר. פה 2 הוא הערך הגבוה ביותר, ולכן מוחזר 'e'.

תוכנית C ++ למציאת הדמות בתדירות הגבוהה ביותר

להלן תוכנית C ++ למציאת הדמות בתדירות הגבוהה ביותר במחרוזת:

קָשׁוּר: כיצד לספור את המופעים של דמות נתונה במחרוזת

// C ++ תוכנית למציאת הדמות
// בעל התדר הגבוה ביותר במחרוזת
#לִכלוֹל 
#לִכלוֹל 
#define ASCII_SIZE 256
באמצעות std namespace;
char maxFrequencyChar (str string)
{
// מערך לאחסון תדירות של כל תו
// אתחל את התדירות של כל תו כ- 0
תדר int [ASCII_SIZE] = {0};
// מציאת אורך מחרוזת הקלט
int lenOfStr = str.length ();
// אתחל את המשתנה maxFrequency
int maxFrequency = -1;
// אתחל את המשתנה maxFrequencyChar
char maxFrequencyChar;
// חצייה ותחזוקה של
// תדירות של כל תו
עבור (int i = 0; i {
תדר [str [i]] ++;
אם (maxFrequency {
maxFrequency = תדר [str [i]];
maxFrequencyChar = str [i];
}
}
החזר maxFrequencyChar;
}
// קוד הנהג
int main ()
{
string str1 = "איזו מכשפה איזו?";
cout << "str1:" << str1 << endl;
cout << "הדמות בתדירות הגבוהה ביותר היא:" << maxFrequencyChar (str1) << endl;
מחרוזת str2 = "הוא זרק שלוש זריקות עונשין";
cout << "str2:" << str2 << endl;
cout << "הדמות בתדירות הגבוהה ביותר היא:" << maxFrequencyChar (str2) << endl;
string str3 = "אדי ערך את זה";
cout << "str3:" << str3 << endl;
cout << "הדמות בתדירות הגבוהה ביותר היא:" << maxFrequencyChar (str3) << endl;
מחרוזת str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "הדמות בתדירות הגבוהה ביותר היא:" << maxFrequencyChar (str4) << endl;
מחרוזת str5 = "היא רואה גבינה";
cout << "str5:" << str5 << endl;
cout << "הדמות בתדירות הגבוהה ביותר היא:" << maxFrequencyChar (str5) << endl;
}

תְפוּקָה:

str1: איזו מכשפה איזו?
הדמות בתדירות הגבוהה ביותר היא: h
str2: הוא זרק שלוש זריקות עונשין
הדמות בתדירות הגבוהה ביותר היא: ה
str3: אדי ערך את זה
הדמות בתדירות הגבוהה ביותר היא: ד
str4: Makeuseof
הדמות בתדירות הגבוהה ביותר היא: ה
str5: היא רואה גבינה
הדמות בתדירות הגבוהה ביותר היא: ה

תוכנית פייתון למציאת הדמות בתדירות הגבוהה ביותר

להלן תוכנית פייתון לאיתור הדמות בתדירות הגבוהה ביותר במחרוזת:

קָשׁוּר: כיצד להפוך מחרוזת ב- C ++, Python ו- JavaScript

# תוכנית פייתון למציאת הדמות
# בעל התדר הגבוה ביותר במחרוזת
ASCII_SIZE = 256
def maxFrequencyChar (str):
# מערך לאחסון תדירות של כל תו
# אותם את התדירות של כל תו כ- 0
תדר = [0] * ASCII_SIZE
# אתחל את המשתנה maxFrequency
maxFrequency = -1
# אתחל את המשתנה maxFrequencyChar
maxFrequencyChar = "
# חצייה ותחזוקה של
תדירות # של כל תו
עבור אני ב str:
תדר [ord (i)] + = 1
עבור אני ב str:
אם maxFrequency maxFrequency = תדר [ord (i)]
maxFrequencyChar = אני
החזר maxFrequencyChar
# קוד נהג
str1 = "איזו מכשפה איזו?"
הדפס ("str1:", str1)
הדפס ("התו בתדירות הגבוהה ביותר הוא:", maxFrequencyChar (str1))
str2 = "הוא זרק שלוש זריקות עונשין"
הדפס ("str2:", str2)
הדפס ("התו בתדירות הגבוהה ביותר הוא:", maxFrequencyChar (str2))
str3 = "אדי ערך את זה"
הדפס ("str3:", str3)
הדפס ("התו בתדירות הגבוהה ביותר הוא:", maxFrequencyChar (str3))
str4 = "Makeuseof"
הדפס ("str4:", str4)
הדפס ("התו בתדירות הגבוהה ביותר הוא:", maxFrequencyChar (str4))
str5 = "היא רואה גבינה"
הדפס ("str5:", str5)
הדפס ("התו בתדירות הגבוהה ביותר הוא:", maxFrequencyChar (str5))

תְפוּקָה:

str1: איזו מכשפה איזו?
הדמות בתדירות הגבוהה ביותר היא: h
str2: הוא זרק שלוש זריקות עונשין
הדמות בתדירות הגבוהה ביותר היא: ה
str3: אדי ערך את זה
הדמות בתדירות הגבוהה ביותר היא: ד
str4: Makeuseof
הדמות בתדירות הגבוהה ביותר היא: ה
str5: היא רואה גבינה
הדמות בתדירות הגבוהה ביותר היא: ה

תוכנית ג למציאת הדמות בתדירות הגבוהה ביותר

להלן תוכנית C למציאת הדמות בתדירות הגבוהה ביותר במחרוזת:

קָשׁוּר: כיצד למצוא תנועות, עיצורים, ספרות ודמויות מיוחדות במחרוזת

// תוכנית C למציאת הדמות
// בעל התדר הגבוה ביותר במחרוזת
#לִכלוֹל 
#לִכלוֹל 
#define ASCII_SIZE 256
באמצעות std namespace;
char maxFrequencyChar (char * str)
{
// מערך לאחסון תדירות של כל תו
// אתחל את התדירות של כל תו כ- 0
תדר int [ASCII_SIZE] = {0};
// מציאת אורך מחרוזת הקלט
int lenOfStr = strlen (str);
// אתחל את המשתנה maxFrequency
int maxFrequency = 0;
// אתחל את המשתנה maxFrequencyChar
char maxFrequencyChar;
// חצייה ותחזוקה של
// תדירות של כל תו
עבור (int i = 0; i {
תדר [str [i]] ++;
אם (maxFrequency {
maxFrequency = תדר [str [i]];
maxFrequencyChar = str [i];
}
}
החזר maxFrequencyChar;
}
// קוד הנהג
int main ()
{
char str1 [] = "איזו מכשפה איזו?";
printf ("str1:% s", str1);
printf ("התו בתדירות הגבוהה ביותר הוא:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "הוא זרק שלוש זריקות עונשין";
printf ("str2:% s", str2);
printf ("התו בתדירות הגבוהה ביותר הוא:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "אדי ערך את זה";
printf ("str3:% s", str3);
printf ("התו בתדירות הגבוהה ביותר הוא:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("התו בתדירות הגבוהה ביותר הוא:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "היא רואה גבינה";
printf ("str1:% s", str5);
printf ("התו בתדירות הגבוהה ביותר הוא:% c \ ⁠n", maxFrequencyChar (str5));
}

תְפוּקָה:

str1: איזו מכשפה איזו?
הדמות בתדירות הגבוהה ביותר היא: h
str2: הוא זרק שלוש זריקות עונשין
הדמות בתדירות הגבוהה ביותר היא: ה
str3: אדי ערך את זה
הדמות בתדירות הגבוהה ביותר היא: ד
str4: Makeuseof
הדמות בתדירות הגבוהה ביותר היא: ה
str5: היא רואה גבינה
הדמות בתדירות הגבוהה ביותר היא: ה

תוכנית JavaScript למציאת הדמות בתדירות הגבוהה ביותר

להלן תוכנית JavaScript למציאת הדמות בתדירות הגבוהה ביותר במחרוזת:

// תוכנית JavaScript למציאת הדמות
// בעל התדר הגבוה ביותר במחרוזת
תן ל- ASCII_SIZE = 256;
function maxFrequencyChar (str)
{
// מערך לאחסון תדירות של כל תו
// אתחל את התדירות של כל תו כ- 0
תן תדר = מערך חדש (ASCII_SIZE);
עבור (תן i = 0; i {
תדר [i] = 0;
}
// מציאת אורך מחרוזת הקלט
תן lenOfStr = str.length;
עבור (תן i = 0; i {
תדר [str [i] .charCodeAt (0)] + = 1;
}
// אתחל את המשתנה maxFrequency
תן maxFrequency = -1;
// אתחל את המשתנה maxFrequencyChar
תן maxFrequencyChar = ";
// חצייה ותחזוקה של
// תדירות של כל תו
עבור (תן i = 0; i {
אם (maxFrequency {
maxFrequency = תדר [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
החזר maxFrequencyChar;
}
// קוד הנהג
let str1 = "איזו מכשפה היא איזו?";
document.write ("str1:" + str1 + "
");
document.write ("התו בתדירות הגבוהה ביותר הוא:" + maxFrequencyChar (str1) + "
")
let str2 = "הוא זרק שלוש זריקות עונשין";
document.write ("str2:" + str2 + "
");
document.write ("התו בתדירות הגבוהה ביותר הוא:" + maxFrequencyChar (str2) + "
")
let str3 = "אדי ערך את זה";
document.write ("str3:" + str3 + "
");
document.write ("התו בתדירות הגבוהה ביותר הוא:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("התו בתדירות הגבוהה ביותר הוא:" + maxFrequencyChar (str4) + "
")
let str5 = "היא רואה גבינה";
document.write ("str5:" + str5 + "
");
document.write ("התו בתדירות הגבוהה ביותר הוא:" + maxFrequencyChar (str5) + "
")

תְפוּקָה:

str1: איזו מכשפה איזו?
הדמות בתדירות הגבוהה ביותר היא: h
str2: הוא זרק שלוש זריקות עונשין
הדמות בתדירות הגבוהה ביותר היא: ה
str3: אדי ערך את זה
הדמות בתדירות הגבוהה ביותר היא: ד
str4: Makeuseof
הדמות בתדירות הגבוהה ביותר היא: ה
str5: היא רואה גבינה
הדמות בתדירות הגבוהה ביותר היא: ה

לנתח את מורכבות הזמן והמרחב

מורכבות הזמן של maxFrequencyChar () פונקציה היא עַל). מורכבות החלל של maxFrequencyChar () פונקציה היא O (1) כמרחב קבוע (מערך Hash). זה לא תלוי בגודל מחרוזת הקלט.

סימון Big-O נותן לך דרך לחשב כמה זמן ייקח להפעיל את הקוד שלך. זהו אחד המושגים החשובים ביותר לניתוח אלגוריתמים. אם אתה מתכנת, עליך לדעת על Big-O Notation.

יובראג 'צ'נדרה (30 מאמרים פורסמו)

יובראג 'הוא סטודנט לתואר ראשון במדעי המחשב באוניברסיטת דלהי, הודו. הוא נלהב מפיתוח אתרים של Full Stack. כשהוא לא כותב, הוא בוחן את עומק הטכנולוגיות השונות.

עוד מאת יוברג 'צ'נדרה