C++で配列内の各要素のサーパッサー（Surpasser）の数を求めるアルゴリズム

ある配列Aが与えられたとき、各要素の「サーパッサー（surpasser）」の数を求める問題を考えてみましょう。サーパッサーとは、現在注目している要素よりも右側に存在する、その要素より大きい値のことです。

例えば、A = {2, 7, 5, 3, 0, 8, 1} という配列の場合、サーパッサーの数は {4, 1, 1, 1, 2, 0, 0} となります。これは、先頭の「2」の右側には「7・5・3・8」という4つの大きな値が存在するためです。その他の要素についても同じルールで数えていきます。

アルゴリズムの考え方

解法は非常にシンプルです。2重のループを使用し、外側のループで各要素を順に取り上げながら、内側のループでその右側にある要素とすべて比較します。そして、自分より大きい値の個数をカウントし、結果を別の配列に格納していきます。

計算量について

この方法の時間計算量はO(n²)です。配列のサイズが小さい場合は十分実用的ですが、サイズが大きい場合にはマージソートの考え方を応用したO(n log n)の効率的な手法も知られています。ここでは理解しやすい単純なアプローチを採用します。

サンプルコード

#include <iostream>
using namespace std;

void getSurpassers(int arr[], int surpassers[], int n){
    for(int i = 0; i < n; i++){
        int count = 0;
        for(int j = i + 1; j < n; j++){
            if(arr[j] > arr[i])
                count++;
        }
        surpassers[i] = count;
    }
}

void displayArray(int arr[], int n){
    for(int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main() {
    int arr[] = {2, 7, 5, 3, 0, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int surpassers[n];

    cout << "Elements :";
    displayArray(arr, n);

    getSurpassers(arr, surpassers, n);

    cout << "Surpassers:";
    displayArray(surpassers, n);
}

実行結果

Elements :2 7 5 3 0 8 1
Surpassers:4 1 1 1 2 0 0

実行結果から、元の配列 {2, 7, 5, 3, 0, 8, 1} の各要素に対して、右側に存在するより大きい値の個数が正しく {4, 1, 1, 1, 2, 0, 0} と出力されていることが確認できます。最大値である「8」以降の要素は右側にそれより大きい値が存在しないため、0になっている点にも注目してください。