C++でソート済み配列内の要素の出現回数（頻度）を効率的に数える方法

整数型の要素からなるソート済み配列と、ある整数 num が与えられたとき、その要素が配列内に何回出現するか（＝頻度）を求めるのが本記事の目的です。

入力例と出力例

• 入力：int arr[] = {1, 1, 1, 2, 3, 4}、num = 1
  出力：ソート済み配列内の出現回数は − 3
• 入力：int arr[] = {2, 3, 4, 5, 5, 6, -7}、num = 5
  出力：ソート済み配列内の出現回数は − 2
• 入力：int arr[] = {-1, 0, 1, 2, 3}、num = 7
  出力：ソート済み配列内の出現回数は − 0

解法のアプローチ

この問題を解くには複数の方法があります。ここでは「素朴な方法（全走査）」と「二分探索を利用した効率的な方法」の2つを紹介します。

素朴なアプローチ（線形探索）

1. 正負の整数を含む配列と、頻度を調べたい変数 num を宣言します。
2. 配列のサイズを計算し、すべてのデータを関数に渡して処理します。
3. 出現回数を格納する一時変数 count を宣言します。
4. i を 0 から配列サイズまでループさせます。
5. ループ内で num == arr[i] であれば count を 1 増やします。
6. count を返して結果を出力します。

この方法の計算量は O(n) であり、配列全体を一度ずつ走査する必要があります。

効率的なアプローチ（lower_bound / upper_bound を活用）

配列がすでにソートされていることを活かせば、二分探索ベースの lower_bound と upper_bound を使うことで O(log n) の計算量で頻度を求められます。手順は以下の通りです。

1. 配列と変数 num を宣言し、データを関数に渡します。
2. ポインタ first を lower_bound(arr, arr+size, num) として設定します。lower_bound は num 以上の値が最初に現れる位置を返します。
3. first == (arr + size) または *first != num の場合は要素が存在しないため 0 を返します。
4. ポインタ last を upper_bound(first, arr+size, num) として設定します。upper_bound は num より大きい値が最初に現れる位置を返します。
5. count = last - first とすることで出現回数が得られます。
6. count を返して結果を出力します。

サンプルコード（素朴なアプローチ）

#include <iostream>
using namespace std;

int frequency_count(int arr[], int num, int size){
    int count = 0;
    for(int i = 0; i < size; i++){
        if(num == arr[i]){
            count++;
        }
    }
    return count;
}

int main(){
    int arr[] = {1, 1, 1, 2, 3, 4};
    int num = 1;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << "ソート済み配列内の出現回数: " << frequency_count(arr, num, size);
    return 0;
}

出力結果

ソート済み配列内の出現回数: 3

サンプルコード（効率的なアプローチ）

#include <bits/stdc++.h>
using namespace std;

int frequency_count(int arr[], int num, int size){
    int *first = lower_bound(arr, arr + size, num);

    if (first == (arr + size) || *first != num){
        cout << "その要素は配列内に存在しません";
        return 0;
    }

    int *last = upper_bound(first, arr + size, num);
    int count = last - first;
    return count;
}

int main(){
    int arr[] = {1, 1, 1, 2, 3, 4};
    int num = 1;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << "ソート済み配列内の出現回数: " << frequency_count(arr, num, size);
    return 0;
}

出力結果

ソート済み配列内の出現回数: 3

まとめ

線形探索による素朴な方法は実装が簡単ですが O(n) の計算量がかかります。一方、配列がソート済みである場合は lower_bound と upper_bound を組み合わせることで O(log n) で頻度を求められます。大規模なデータを扱う場合や頻繁に検索を行う場合には、後者の効率的なアプローチを選ぶことをおすすめします。