C++で配列内の要素の出現頻度をカウントする方法

はじめに

重複した値を含む整数型の配列が与えられ、その中に存在する各要素（異なる値）の出現頻度を計算して結果を出力することが課題です。

入力 − int arr[] = {1, 1, 2, 3, 4, 1, 2, 3}

出力 −

frequency of 1 is: 3
frequency of 2 is: 2
frequency of 3 is: 2
frequency of 4 is: 1

入力 − int arr[] = {2, 3, 4, 1, 5}

出力 −

frequency of 1 is: 1
frequency of 2 is: 1
frequency of 3 is: 1
frequency of 4 is: 1
frequency of 5 is: 1

プログラムで使用するアプローチ

この問題には複数の解法があります。コードの書きやすさを重視した方法もあれば、計算量の面で効率的な方法もあります。まずは、実装がシンプルなアプローチから見ていきましょう。

方法1：フラグ配列を使う方法（時間計算量 O(n²)）

• 整数型の配列を作成します。
• size()関数を使って配列のサイズを求めます。
• 配列と同じサイズのbool型配列（ここではcheck）を作成します。
• i を 0 から size 未満までループさせます。
• ループ内で check[i] = 0 を設定します。
• 再び i を 0 から size 未満までループさせます。
• ループ内で check[i] == 1 の場合は continue でスキップします。
• 出現回数を保持する変数 count を宣言し、1 で初期化します。
• j を i+1 から size 未満までループさせます。
• ループ内で arr[i] == arr[j] であれば check[j] を 1 に設定し、count を 1 増やします。
• count の値を出力します。

方法2：unordered_map を使う方法（平均時間計算量 O(n)）

• 整数型の配列を作成します。
• size()関数を使って配列のサイズを求めます。
• unordered_map 型の変数（ここではum）を作成します。
• i を 0 から size 未満までループさせます。
• ループ内で um[arr[i]]++ を実行して出現回数をカウントします。
• 範囲ベースfor文で um の全要素を走査します。
• ループ内で各要素の頻度を出力します。

例：フラグ配列を使った実装

#include <bits/stdc++.h>
using namespace std;
int frequency(int arr[], int size){
    bool check[size];
    for(int i=0;i<size;i++){
        check[i] = 0;
    }
    for(int i=0; i<size; i++){
        if(check[i]== 1){
            continue;
        }
        int count = 1;
        for(int j = i+1; j<size; j++){
            if (arr[i] == arr[j]){
                check[j] = 1;
                count++;
            }
        }
        cout<<"frequency of "<<arr[i]<<" is: " << count << endl;
    }
}
int main(){
    int arr[] = {1, 2, 3, 1, 2, 3};
    //calculate the size of an array
    int size = sizeof(arr) / sizeof(arr[0]);
    //call function to calculate the frequency
    frequency(arr, size);
    return 0;
}

出力

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

frequency of 1 is: 2
frequency of 2 is: 2
frequency of 3 is: 2

例：unordered_map を使った実装

#include <bits/stdc++.h>
using namespace std;
void frequency(int arr[], int size){
    unordered_map<int, int> um;
    for (int i = 0; i < size; i++){
        um[arr[i]]++;
    }
    for (auto x : um){
        cout<<"frequency of "<<x.first<<" is: "<< x.second<< endl;
    }
}
int main(){
    int arr[] = {1, 2, 3, 1, 2, 3 };
    int size = sizeof(arr) / sizeof(arr[0]);
    frequency(arr, size);
    return 0;
}

出力

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

frequency of 3 is: 2
frequency of 1 is: 2
frequency of 2 is: 2

まとめ

フラグ配列を使う方法は追加のコンテナが不要でロジックが直感的に理解しやすい反面、二重ループを使用するため時間計算量は O(n²) となり、大きな配列では処理が遅くなります。一方、unordered_map を使う方法はハッシュテーブルを利用するため平均 O(n) で高速に動作しますが、unordered_map は要素の順序を保証しないため、出力順序が入力順と異なる場合がある点に注意が必要です。順序を保ちたい場合は map を使うとキーの昇順で出力できます。