C++で文字列内の2番目に頻度の高い文字を見つけるプログラム

この問題では、文字列 str が与えられます。私たちの課題は、C++で文字列内に2番目に出現頻度が高い文字を見つけるプログラムを作成することです。

入力例で問題を理解しよう

入力

str = "abaacabcba"

出力

'b'

この例では、文字 'a' が5回、'b' が3回、'c' が2回出現しています。最も頻度が高いのは 'a' なので、2番目に頻度の高い文字である 'b' が出力されます。

解決アプローチ

文字列の中で2番目に頻度の高い文字を見つけるには、以下の手順を実行します。

• まず、各文字の出現回数を格納するためのカウント配列（charFreq）を用意します。
• 文字列を1文字ずつ走査しながら、対応する配列要素のカウントを増やしていきます。
• その後、配列を走査して最大頻度（maxFreq）と2番目の頻度（secFreq）を持つ文字を特定します。
• 最後に、2番目に頻度の高い文字を結果として返します。

このアルゴリズムの時間計算量は O(n) であり、非常に効率的です。ここで n は文字列の長さです。

ソリューションの動作を示すプログラム

例

#include <iostream>
#include <string.h>
using namespace std;

char findSecFreqChar(string str){
    int charFreq[256] = {0};
    for (int i = 0; i < str.length(); i++)
        (charFreq[str[i]])++;

    int maxFreq = 0, secFreq = 0;
    for (int i = 0; i < 256; i++){
        if (charFreq[i] > charFreq[maxFreq]){
            secFreq = maxFreq;
            maxFreq = i;
        }
        else if (charFreq[i] > charFreq[secFreq] &&
        charFreq[i] != charFreq[maxFreq])
        secFreq = i;
    }
    return secFreq;
}

int main(){
    string str = "tutorialspoint";
    char secFreqChar = findSecFreqChar(str);
    cout << "文字列の中で2番目に頻度の高い文字は "<<secFreqChar;
    return 0;
}

出力

文字列の中で2番目に頻度の高い文字は i

コードの解説

このプログラムでは、サイズ256の整数配列 charFreq を宣言し、すべての要素を0で初期化しています。これにより、ASCIIコードのすべての文字に対応できます。

最初のループでは、文字列の各文字について、そのASCII値をインデックスとして配列のカウントを1ずつ増やしていきます。

次のループでは、配列全体を走査し、現在の文字の頻度が最大頻度より大きい場合は、それまでの最大値を2番目の値として保存し、新しい最大値を更新します。そうでない場合でも、現在の頻度が2番目の頻度より大きく、かつ最大頻度と異なる場合は、2番目の頻度を更新します。

最終的に、2番目に頻度の高い文字のASCII値が返され、main関数で画面に表示されます。