C++で配列内の最頻出要素を求める方法

配列が与えられたとき、その中で最も多く出現する要素(最頻出要素)を見つける問題を考えてみましょう。まずは具体例から確認します。

入力例と出力例

入力

arr = [1, 2, 3, 3, 2, 2, 1, 1, 2, 3, 4]

出力

2

上記の配列では、2 が4回出現しており、他のどの要素よりも出現回数が多くなっています。

アルゴリズム1:ハッシュマップを使う方法

• 配列を初期化します。
• 各要素の出現回数を格納するためのマップ(unordered_map)を初期化します。
• 配列を走査しながら各要素の出現回数を数え、マップに保存します。
• マップを走査し、最も出現回数の多い要素を見つけます。
• その要素を返します。

この方法の時間計算量は O(n)、空間計算量は O(n) となり、効率的に最頻出要素を求められます。

アルゴリズム2:ソートを使う方法

• 配列を初期化します。
• 与えられた配列をソートします。
• 最大出現回数・結果・現在の要素の出現回数を保持する変数を用意します。
• ソート後は同じ要素が必ず隣り合うため、配列を一度走査するだけで最大出現回数の要素を見つけられます。
• 結果を返します。

この方法の時間計算量は O(n log n) です。追加のメモリをほとんど使わずに済む点が特徴です。

C++での実装

以下は、アルゴリズム1(ハッシュマップ方式)をC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int getMostFrequentNumber(int arr[], int n) {
    unordered_map<int, int> elements;
    for (int i = 0; i < n; i++) {
        elements[arr[i]]++;
    }
    int maxCount = 0, res = -1;
    for (auto i : elements) {
        if (maxCount < i.second) {
            res = i.first;
            maxCount = i.second;
        }
    }
    return res;
}
int main() {
    int arr[] = { 1, 2, 3, 3, 2, 2, 1, 1, 2, 3, 4 };
    int n = 11;
    cout << getMostFrequentNumber(arr, n) << endl;
    return 0;
}

実行結果

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

2

このように、ハッシュマップを活用することで、配列内の最頻出要素を線形時間で簡単に求めることができます。