C++で配列内の最小値の出現回数（頻度）を求める方法

この記事では、配列の中で最小の要素が何回出現するか（頻度）を求める方法を解説します。

例として、配列の要素が [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10] である場合を考えてみましょう。この配列の最小値は 3 であり、その出現回数は 4 回です。したがって、出力は 4 となります。

解決のアプローチ

この問題を解く手順は非常にシンプルで、以下の2ステップで構成されます。

1. まず、配列全体を走査して最小値を見つける
2. 次に、その最小値と一致する要素の個数を数える

この方法の時間計算量は O(n) であり、配列を2回走査しますが、線形時間で処理が完了するため効率的です。

サンプルコード

#include<iostream>
using namespace std;

// 配列内の最小値を求める関数
int min_element(int arr[], int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min)
            min = arr[i];
    }
    return min;
}

// 最小値の出現回数を数える関数
int smallestNumFreq(int *arr, int n) {
    int minimum = min_element(arr, n);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == minimum)
            count++;
    }
    return count;
}

int main() {
    int arr[] = {5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Frequency of smallest element: " << smallestNumFreq(arr, n);
}

実行結果

Frequency of smallest element: 4

コードの解説

このプログラムは、2つの補助関数と main 関数で構成されています。

min_element 関数： 最初の要素を仮の最小値とし、残りの要素と順に比較することで、配列内の最小値を特定します。

smallestNumFreq 関数： min_element 関数で取得した最小値をもとに、配列を再度走査し、最小値と一致する要素をカウントします。

main 関数： サンプル配列を定義し、sizeof 演算子を使って要素数を計算した上で、smallestNumFreq 関数を呼び出して結果を表示します。

なお、配列を1回の走査で最小値と出現回数を同時に求める実装も可能です。その場合は、より小さい値が見つかった時点でカウントをリセットし、等しい値が見つかった場合にカウントを増やすことで、計算量をさらに最適化できます。