最大出现字符


难度级别 易得奖学金
经常问 亚马逊 摩根士丹利 PayU 百会
哈希

给定大小为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. 打印答案。

用于最大出现字符的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的哈希表。
  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的哈希表,因为总共有256个ASCII字符。

但是,例如,如果在问题中给出了输入字符串仅包含小写字母的问题,那么我们本可以使用大小为26的哈希表,只是因为字典中只有26个小写字母。

參考資料