【C++】配列内の全要素の出現頻度をO(n)時間・O(1)の追加メモリでカウントする方法

1からnまでの範囲の値を持つ要素からなる配列が与えられます。一部の要素は複数回出現し、逆に一度も出現しない要素もあります。ここでの課題は、O(n)の計算時間とO(1)の追加メモリという制約のもとで、すべての要素の出現頻度を求めることです。

入力例1

Arr[]= { 1,2,2,3,4,4,4,5 }

出力例1

1→ 1, 2→ 2, 3→ 1, 4→ 3, 5→ 1

解説：最大値は5であり、出力は各要素が配列内に出現した回数を示しています。

入力例2

Arr[]= { 1,4,4,5,5,5,5 }

出力例2

1→ 1, 2→ 0, 3→ 0, 4→ 2, 5→ 4

解説：最大値は5であり、出力は各要素が配列内に出現した回数を示しています。

プログラムで使用しているアプローチ

• このプログラムは、1〜10の範囲の数値を含む配列に対して動作します。

• 関数printfrequency(int arr[], int n)は、配列とそのサイズnを受け取り、配列内に存在する1〜10の各数値の出現回数を出力します。

• まずarr[i]=arr[i]-1として各値を1つ減らすことで、インデックスiに「数値i+1」の頻度を格納できるようにします（1は0、2は1、……10は9に対応）。

• 次にforループを使い、各要素についてarr[arr[i]%10]に10を加算します。数値は1〜10の範囲なので、1を引いた後の値は0〜9となり、num%10はnumそのものと一致します。

• ある数値iが配列中にx回出現すると、対応する位置には10がx回加算されます。

• 最後にforループでarr[i]/10を出力することで、インデックスiに対応する数値i+1の頻度が求められます。

このテクニックのポイントは、1つの配列要素に「元の値」と「出現回数」という2つの情報を同時に埋め込んでいる点です。10の倍数を加算しても剰余演算（%）で元の値を取り出すことができ、商（/）からは出現回数が得られるため、補助配列が一切不要になります。

実装例

#include<bits/stdc++.h>
using namespace std;
void printfrequency(int arr[],int n){
    int i=0;
    //1は0に、2は1に……10は9に対応するため、arr[i]には数値i+1の出現回数が格納される
    for ( i =0; i<n; i++)
       arr[i] = arr[i]-1;
    //数値は1〜10の範囲なので10を加算する（num%10はnumそのものになる）
    for (i=0; i<n; i++)
       arr[arr[i]%10] = arr[arr[i]%10] + 10;
    for (i =0; i<10; i++)
       cout << i + 1 << " -> " << arr[i]/10 << endl;
}
int main(){
    int arr[] = {2, 3, 3, 2, 5, 6, 7, 7, 7, 8, 8, 9, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    printfrequency(arr,n);
    return 0;
}

出力

1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1
6 -> 1
7 -> 3
8 -> 2
9 -> 2
10 -> 0

計算量

時間計算量はO(n)です。配列を数回走査するだけで処理が完了します。
追加空間計算量はO(1)です。頻度情報は元の配列自体に埋め込まれるため、補助的な記憶域は一切不要です。