אופי מקסימלי המתרחש


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית מורגן סטנלי PayU Zoho
בליל מחרוזת

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

דוגמה

קלט:

מחרוזת s = "מבחן"

פלט:

התו המקסימלי המופיע הוא 't'.

גישה 1: שימוש במיון

רעיון מרכזי

ראשית נמיין את המערך ואז נספור את התדירות של כל אלמנט ונקח את אותה תו שספירתו מקסימאלית.

אלגוריתם לדמות מקסימאלית המתרחשת

  1. הכריז על משתנה max_count אשר יאחסן את המספר המקסימלי.
  2. אתחל ספירת משתנים = 1 שתאחסן את ספירת התו הנוכחי.
  3. הצהיר על משתנה אשר ישמור את תשובתנו.
  4. הכריז על משתנה n המאחסן את אורך מחרוזת הקלט.
  5. מיין את מחרוזת הקלט.
  6. הפעל לולאה עבור אני בטווח 1 עד n
    1. אם אני שווה ל- n או s [i] אינו שווה ל- s [i-1]
      1. אם max_count הוא פחות מ- count, הקצה max_count = count ו- ans = s [i-1].
      2. הקצאת ספירה = 1.
    2. ספירת תוספות אחרת ב -1.
  7. הדפס ans.

תוכנית C ++ לתו המקסימלי המתרחש

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int n = s.length();
    sort(s.begin(), s.end());
    int max_count = 0;
    int count = 1;
    char ans;
    for (int i = 1; i <= n; i++)
    {
        if ((i == n) || (s[i] != s[i - 1]))
        {
            if (max_count < count)
            {
                max_count = count;
                ans = s[i - 1];
            }
            count = 1;
        }
        else
        {
            count++;
        }
    }
    cout <<"Maximum occurring character is "<< ans << endl;
    return 0;
}
tutorialcup
Maximum occurring character is t

תוכנית JAVA לתו המקסימלי המתרחש

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner in = new Scanner(System. in);
      String k = in.nextLine();
      char tempArray[] = k.toCharArray(); 
        Arrays.sort(tempArray); 
        String s = new String(tempArray);
        int n = s.length();
        int max_count = 0;
        int count = 1;
        char ans = '-';
        for (int i = 1; i <= n; i++)
        {
            if ((i == n) || (s.charAt(i) != s.charAt(i - 1)))
            {
                if (max_count < count)
                {
                    max_count = count;
                    ans = s.charAt(i-1);
                }
                count = 1;
            }
            else
            {
                count++;
            }
        }
    System.out.println("Maximum occurring character is "+ans);
  }
}

whattodo
Maximum occurring character is o

ניתוח מורכבות לדמות מקסימאלית המתרחשת

מורכבות זמן

מיון המחרוזת לוקח זמן O (N * logN) ואחרי זה אנו עוברים את המחרוזת פעם אחת. אז מורכבות הזמן הכוללת היא O (N * logN + N) שזהה ל- O (N * logN).

מורכבות חלל

לא השתמשנו בשום שטח נוסף ולכן מורכבות החלל היא O (1).

גישה 2: שימוש בחשיש

רעיון מרכזי

נאחסן את התדירות של כל תו בטבלת hash ולאחריו ניקח את התו בתדר המרבי.

אלגוריתם לדמות מקסימאלית המתרחשת

  1. אתחל את טבלת החשיש בגודל 256 עם אפסים.
  2. חזר על מחרוזת הקלט ושמור את התדירות של כל אלמנט בטבלת החשיש.
  3. קח את התו בתדירות המרבית כתשובה.
  4. הדפיסו את התשובה.

להבין עם דוגמא

מחרוזת קלט S = ”tutorialcup”

לאחר איטרציה של מחרוזת הקלט, טבלת החשיש תיראה כך:

אופי מקסימלי המתרחש

כאן תווים מאוחסנים על פי ערכי ASCII שלהם.

תוכנית C ++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    vector<int> hash_table(256, 0);
    int n = s.length();
    for (int i = 0; i < n; i++)
    {
        hash_table[s[i]]++;
    }
    int max_count = 0;
    char ans;
    for (int i = 0; i < 256; i++)
    {
        if (hash_table[i] > max_count)
        {
            max_count = hash_table[i];
            ans = i;
        }
    }
    cout <<"Maximum occurring character is "<< ans << endl;
    return 0;
}
programming
Maximum occurring character is g

תוכנית JAVA

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner in = new Scanner(System. in);
      String s = in.nextLine();
        int[] hash_table = new int[256];
        int n = s.length();
        for (int i = 0; i < n; i++)
        {
            hash_table[s.charAt(i)]++;
        }
        int max_count = 0;
        char ans='a';
        for (int i = 0; i < 256; i++)
        {
            if (hash_table[i] > max_count)
            {
                max_count = hash_table[i];
                ans = (char)i;
            }
        }
    System.out.println("Maximum occurring character is "+ans);
  }
}


learning
Maximum occurring character is n

ניתוח מורכבות לדמות מקסימאלית המתרחשת

מורכבות זמן

כפי שאנו חוזרים על מחרוזת הקלט פעם אחת בלבד, כך מורכבות הזמן היא O (N).

מורכבות חלל

אנו משתמשים בטבלת hash בגודל 256 ללא קשר לאורך מחרוזת הקלט. אז מורכבות החלל היא O (1).

הערה: לא מצוין בשאלה איזה סוג תווים המחרוזת מכילה, אז לקחנו טבלת hash בגודל 256 מכיוון שיש בסך הכל 256 תווי ASCII.

אך לדוגמא, אם ניתן בשאלה שמחרוזת הקלט מכילה רק אלפביתים קטנים, היינו יכולים להשתמש בטבלת חשיש בגודל 26 רק מכיוון שיש רק 26 אלפביתים קטנים.

הפניות