문자열에서 최대 발생 문자

난이도 쉽게
자주 묻는 질문 아마존 모건 스탠리 (Morgan Stanley) 알레그로 조호 (Zoho)
해시 조회수 64

소문자를 포함하는 크기 n의 문자열이 제공됩니다. 문자열에서 최대 발생 문자를 찾아야 합니다. 최대 발생이 있는 문자가 두 개 이상 있는 경우 아무 문자나 인쇄하십시오.

입력:

문자열 s =”test”

출력:

최대 발생 문자는 't'입니다.

접근 방식 1 : 정렬 사용

주요 아이디어

먼저 배열을 정렬 한 다음 각 요소의 빈도를 계산하고 개수가 최대 인 해당 문자를 가져옵니다.

최대 발생 문자 알고리즘

  1. 최대 개수를 저장할 변수 max_count를 선언합니다.
  2. 현재 문자 수를 저장할 변수 count = 1을 초기화합니다.
  3. 답변을 저장할 변수 ans를 선언하십시오.
  4. 입력 문자열의 길이를 저장하는 변수 n을 선언하십시오.
  5. 입력 문자열을 정렬합니다.
  6. 1에서 n 사이의 I에 대해 루프 실행
    1. I가 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 : 해싱 사용

주요 아이디어

각 문자의 빈도를 해시 테이블에 저장하고 그 후 최대 빈도의 문자를 가져옵니다.

최대 발생 문자 알고리즘

  1. 크기가 256 인 해시 테이블을 XNUMX으로 초기화합니다.
  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)입니다.

공간 복잡성

입력 문자열의 길이에 관계없이 256 크기의 해시 테이블을 사용하고 있습니다. 따라서 공간 복잡성은 O (1)입니다.

참고 : 문자열에 어떤 유형의 문자가 포함되어 있는지 질문에 지정되지 않았으므로 총 256 개의 ASCII 문자가 있기 때문에 256 크기의 해시 테이블을 사용했습니다.

그러나 예를 들어 입력 문자열에 소문자 알파벳 만 포함되어 있다는 질문에서 주어진 경우 사전에 소문자 26 개만 있기 때문에 크기 26의 해시 테이블을 사용할 수 있습니다.

참조

Translate »
1