C++でO(n)未満の時間で範囲制限された配列内の各要素の頻度を求める方法

整数が格納された配列A（サイズn）が与えられているとします。この課題は、O(n)未満の計算量で配列内のすべての要素の出現頻度を求めることです。ただし、要素の値はあらかじめある上限値M未満に制限されているものとします。

この問題は、配列がソート済み（昇順）であることを前提とすれば、二分探索（バイナリサーチ）の考え方を応用することで効率的に解けます。

アルゴリズムの基本的な考え方

ここでは分割統治法にもとづく再帰的なアプローチを採用します。手順は以下のとおりです。

1. 着目している区間の両端の要素を比較します。
2. 両端の要素が一致している場合、配列はすでにソート済みであるため、その区間内のすべての要素が同一であることが保証されます。このとき、その要素の頻度へ区間の長さ（right − left + 1）を一括して加算します。
3. 両端の要素が異なる場合は、区間を中央（mid）で2つに分割し、それぞれの部分区間に対して再帰的に同じ処理を適用します。

同一の要素が連続する区間は一度の判定でまとめて処理できるため、要素の種類が限られている配列では、全体の計算量をO(n)未満に抑えることができます。

C++による実装例

#include<iostream>
#include<vector>
using namespace std;
void calculateFreq(int arr[], int left, int right, vector<int>& frequency) {
   if (arr[left] == arr[right])
      frequency[arr[left]] += right - left + 1;
   else {
      int mid = (left + right) / 2;
      calculateFreq(arr, left, mid, frequency);
      calculateFreq(arr, mid + 1, right, frequency);
   }
}
void getAllFrequency(int arr[], int n) {
   vector<int> frequency(arr[n - 1] + 1, 0);
   calculateFreq(arr, 0, n - 1, frequency);
   for (int i = 0; i <= arr[n - 1]; i++)
      if (frequency[i] != 0)
         cout << "Frequency of element " << i << " is " << frequency[i] << endl;
}
int main() {
   int arr[] = { 10, 10, 10, 20, 30, 30, 50, 50, 80, 80, 80, 90, 90, 99 };
   int n = sizeof(arr) / sizeof(arr[0]);
   getAllFrequency(arr, n);
}

実行結果

Frequency of element 10 is 3
Frequency of element 20 is 1
Frequency of element 30 is 2
Frequency of element 50 is 2
Frequency of element 80 is 3
Frequency of element 90 is 2
Frequency of element 99 is 1

計算量の評価

このアルゴリズムの計算量は、異なる要素の種類数をkとすると O(min(n, k・log n)) で評価できます。要素の値の範囲がM未満に制限されているため k ≤ M となり、重複が多い配列では多くの区間を一括処理できるので、線形時間O(n)よりも高速に動作します。一方、すべての要素が互いに異なる最悪ケースではO(n)程度かかる点には注意が必要です。

なお、この手法は「配列が昇順にソートされていること」「要素の値の範囲が有限（M未満）であること」が前提条件となります。これらの条件を満たす場合にのみ、本アルゴリズムの恩恵を受けられます。