配列内で複数回出現する要素を見つける方法【C++実装例】

問題の概要

本記事では、配列の中から出現回数が2回以上の要素をすべて見つける問題を解説します。

例として、次の配列を考えてみましょう。

{1, 5, 2, 5, 3, 1, 5, 2, 7}

この場合、1は2回、5は3回、2は2回出現しており、それ以外の要素（3と7）はそれぞれ1回しか登場しません。したがって、求める出力は {1, 5, 2} となります。

アルゴリズム

この問題は、ハッシュマップ（連想配列）を利用することで効率的に解けます。基本的な流れは以下の通りです。

moreFreq(arr, n)

Begin
    キーと値がともに int 型のマップを定義する
    配列 arr の各要素 e に対して、以下を実行する
        マップ内の該当キーの値（出現回数）を1増やす
    繰り返し終了
    各キーについて値が1より大きい場合、そのキーを出力する
End

まず配列を一度走査して各要素の出現回数をマップに記録し、その後マップを走査して出現回数が1を超えるキーだけを出力します。

C++による実装例

以下は、C++ の std::map を使った具体的な実装です。

#include <iostream>
#include <map>
using namespace std;

void moreFreq(int arr[], int n){
    map<int, int> freq_map;
    for(int i = 0; i<n; i++){
        freq_map[arr[i]]++; // 出現回数をカウントアップ
    }
    for (auto it = freq_map.begin(); it != freq_map.end(); it++) {
        if (it->second > 1)
            cout << it->first << " ";
    }
}

int main() {
    int arr[] = {1, 5, 2, 5, 3, 1, 5, 2, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Frequency more than one: ";
    moreFreq(arr, n);
}

実行結果

Frequency more than one: 1 2 5

計算量について

std::map は内部で平衡二分探索木（赤黒木）を使用しているため、挿入や検索の計算量は O(log n) です。そのため、全体の時間計算量は O(n log n)、空間計算量は O(n) となります。

なお、順序が不要であれば unordered_map を使うことで、平均 O(1) でのアクセスが可能になり、全体の計算量を O(n) まで抑えられます。用途に応じて使い分けるとよいでしょう。