C++で最頻出要素を求めるプログラムの作成方法：整数配列から最も多く現れる値を見つける

サイズNの整数型配列が与えられたとき、その配列の中で最も頻繁に出現する要素（最頻出要素）を見つけることを考えましょう。例えば、以下のようなケースが挙げられます。

入力例と出力例

例1

入力：

N = 8
A[ ] = {1,2,4,3,3,1,1,5}

出力：

1

解説： この配列の中で最も多く出現している数は「1」です。したがって、出力は「1」となります。

例2

入力：

N = 6
A[ ] = {1,4,4,4,1,1}

出力：

1 または 4

解説： この配列では「1」と「4」が同数（3回ずつ）出現しており、どちらも最頻出要素です。この場合、どちらか一方を返せば正解となります。

問題を解くためのアプローチ

与えられた配列には複数の整数が含まれており、その中から最も頻度の高い要素を見つける必要があります。この問題を線形時間 O(n)・線形空間 O(n) で効率的に解くには、ハッシュマップ（連想配列）を使うアプローチが有効です。

具体的には、C++のSTLライブラリに含まれる unordered_map を使用し、「キー＝配列の要素」「バリュー＝その出現回数」というキー・バリューのペアでマップを作成します。マップを走査しながら最大の出現回数を持つ数を特定し、それを出力として返します。

アルゴリズムの手順

• サイズNの配列を入力として受け取ります。
• 整数型関数 maxOccurrence(int A[], int size) を定義します。この関数は配列とそのサイズを引数に取り、最大頻度を持つ数を返します。
• 配列の全要素についてハッシュマップを作成します。キーには要素そのものを、バリューにはその出現回数（頻度）を格納します。
• マップを反復処理し、最も高い頻度を持つ要素が見つかったら、その数を結果として返します。配列内に該当する要素が存在しない場合は「-1」を返します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
int maxOccurrence(int A[], int size){
    int mxcount=0;
    int res=-1;
    unordered_map<int,int>mp;
    for(int i=0;i<size;i++){
        mp[A[i]]++;
    }
    for(auto x:mp){
        if(x.second>mxcount){
            res= x.first;
            mxcount=x.second;
        }
    }
    return res;
}
int main(){
    int N=6;
    int A[N]= {1,4,4,4,2,1};
    int ans= maxOccurrence(A,N);
    cout<<ans<<endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

4

この配列では「4」の出現回数が3回であり、他のどの数よりも高い頻度となっているため、「4」が出力されます。

まとめ

ハッシュマップを活用することで、配列の各要素の出現回数を一度の走査で記録でき、計算量O(n)という高效な処理が可能になります。要素の検索や集計が必要な場面では、unordered_mapは非常に強力なツールなので、ぜひ使いこなせるようにしておきましょう。