문자열에서 최대 발생 문자

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

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

차례

예

입력:

문자열 s =”test”

출력:

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

접근 방식 1 : 정렬 사용

주요 아이디어

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

최대 발생 문자 알고리즘

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

주요 아이디어

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

최대 발생 문자 알고리즘

크기가 256 인 해시 테이블을 XNUMX으로 초기화합니다.
입력 문자열을 반복하고 해시 테이블에 각 요소의 빈도를 저장합니다.
최대 빈도를 가진 캐릭터를 답으로 취하십시오.
답을 인쇄하십시오.

예를 들어 이해

입력 문자열 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의 해시 테이블을 사용할 수 있습니다.

참조