输入字符串中出现的最大字符数|s2

2021年3月13日15:38:11 发表评论 864 次浏览

本文概述

给定一个包含小写字符的字符串。任务是在输入字符串中打印出现的最大字符。如果2个或更多字符出现相同的次数, 则按字典(字母顺序)最低(第一个)字符打印。

例子:

输入:测试样本输出:e" t", " e"和" s"出现2次, 但" e"是字典上最小的字符。输入:示例程序输出:a

推荐:请尝试以下方法{IDE}首先, 在继续解决方案之前。

在里面以前文章中, 如果在最大时间范围内出现多个字符, 则将返回任何字符。在这篇文章中, 返回所有字符中按字典顺序最小的字符。

方法:声明一个频率[26]用作哈希表的数组, 用于存储输入字符串中每个字符的频率。迭代字符串并增加计数频率展开]对于每个字符。遍历频率[]从左到右排列, 并跟踪到目前为止具有最大频率的字符。 freq [i]处的值表示字符(i +'a')的频率。

下面是上述方法的实现:

C ++

// C++ implementation to find
// the maximum occurring character in
// an input string which is lexicographically first
#include <bits/stdc++.h>
using namespace std;
  
// function to find the maximum occurring character in
// an input string which is lexicographically first
char getMaxOccurringChar( char str[])
{
     // freq[] used as hash table
     int freq[26] = { 0 };
  
     // to store maximum frequency
     int max = -1;
  
     // to store the maximum occurring character
     char result;
  
     // length of 'str'
     int len = strlen (str);
  
     // get frequency of each character of 'str'
     for ( int i = 0; i < len; i++)
         freq[str[i] - 'a' ]++;
  
     // for each character, where character is obtained by
     // (i + 'a') check whether it is the maximum character
     // so far and accodingly update 'result'
     for ( int i = 0; i < 26; i++)
         if (max < freq[i]) {
             max = freq[i];
             result = ( char )(i + 'a' );
         }
  
     // maximum occurring character
     return result;
}
  
// Driver Code
int main()
{
     char str[] = "sample program" ;
     cout << "Maximum occurring character = "
          << getMaxOccurringChar(str);
     return 0;
}

Java

// Java implementation to find
// the maximum occurring character in
// an input string which is lexicographically first
  
class GFG {
  
// function to find the maximum occurring character in
// an input string which is lexicographically first
     static char getMaxOccurringChar( char str[]) {
         // freq[] used as hash table
         int freq[] = new int [ 26 ];
  
         // to store maximum frequency
         int max = - 1 ;
  
         // to store the maximum occurring character
         char result = 0 ;
  
         // length of 'str'
         int len = str.length;
  
         // get frequency of each character of 'str'
         for ( int i = 0 ; i < len; i++) {
             if (str[i] != ' ' ) {
                 freq[str[i] - 'a' ]++;
             }
         }
  
         // for each character, where character is obtained by
         // (i + 'a') check whether it is the maximum character
         // so far and accodingly update 'result'
         for ( int i = 0 ; i < 26 ; i++) {
             if (max < freq[i]) {
                 max = freq[i];
                 result = ( char ) (i + 'a' );
             }
         }
  
         // maximum occurring character
         return result;
     }
  
// Driver Code
     public static void main(String[] args) {
         char str[] = "sample program" .toCharArray();
         System.out.println( "Maximum occurring character = "
                 + getMaxOccurringChar(str));
     }
} 
  
// This code is contributed by 29AjayKumar

Python3

# Python 3 implementation to find the 
# maximum occurring character in an input 
# string which is lexicographically first
  
# function to find the maximum occurring 
# character in an input string which is 
# lexicographically first
def getMaxOccurringChar( str ):
      
     # freq[] used as hash table
     freq = [ 0 for i in range ( 100 )] 
  
     # to store maximum frequency
     max = - 1
  
     # to store the maximum occurring
     # character length of 'str'
     len__ = len ( str )
  
     # get frequency of each character of 'str'
     for i in range ( 0 , len__, 1 ):
         freq[ ord ( str [i]) - ord ( 'a' )] + = 1
  
     # for each character, where character
     # is obtained by (i + 'a') check whether 
     # it is the maximum character so far and
     # accodingly update 'result'
     for i in range ( 26 ):
         if ( max < freq[i]):
             max = freq[i]
             result = chr ( ord ( 'a' ) + i)
  
     # maximum occurring character
     return result
  
# Driver Code
if __name__ = = '__main__' :
     str = "sample program"
     print ( "Maximum occurring character =" , getMaxOccurringChar( str ))
      
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation to find
// the maximum occurring character in
// an input string which is lexicographically first
   
using System;
class GFG {
   
// function to find the maximum occurring character in
// an input string which is lexicographically first
     static char getMaxOccurringChar( string str) {
         // freq[] used as hash table
         int [] freq = new int [26];
   
         // to store maximum frequency
         int max = -1;
   
         // to store the maximum occurring character
         char result = ( char )0;
   
         // length of 'str'
         int len = str.Length;
   
         // get frequency of each character of 'str'
         for ( int i = 0; i < len; i++) {
             if (str[i] != ' ' ) {
                 freq[str[i] - 'a' ]++;
             }
         }
   
         // for each character, where character is obtained by
         // (i + 'a') check whether it is the maximum character
         // so far and accodingly update 'result'
         for ( int i = 0; i < 26; i++) {
             if (max < freq[i]) {
                 max = freq[i];
                 result = ( char ) (i + 'a' );
             }
         }
   
         // maximum occurring character
         return result;
     }
   
// Driver Code
     public static void Main() {
         string str = "sample program" ;
         Console.WriteLine( "Maximum occurring character = "
                 + getMaxOccurringChar(str));
     }
}

输出如下:

Maximum occurring character = a

时间复杂度:

上)。

辅助空间:

O(1)。

资源: 佩剑面试经验|套装2


木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: