C++で右側にある「次に大きい要素（NGE）」の個数を数える方法

配列とターゲット要素のインデックスが与えられたとき、その要素より右側に存在する、指定された要素よりも大きい値を持つ要素の個数を数える問題を考えてみましょう。まずは具体例から見ていきます。

問題の例

入力：

arr = [2, 3, 5, 1, 4, 2, 6]
index = 3

出力：

3

この例では、ターゲットとなるインデックス 3 の要素は 1 です。その右側には 4、2、6 の 3 つの要素が存在し、これらはすべて 1 より大きいため、答えは 3 となります。

アルゴリズム

• 配列とターゲット要素のインデックスを初期化します。
• インデックスが配列の長さ以上の場合は、無効な入力として -1 を返します。
• 指定されたインデックスの次の要素から配列の末尾まで順に走査するループを作成します。
  • 走査中の要素がターゲット要素より大きければ、カウントを 1 増やします。
• 最終的なカウントを返します。

C++での実装

以下は、上記のアルゴリズムを C++ で実装したコードです。

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

int getNextGreaterElementsCount(int arr[], int n, int index) {
    // インデックスが範囲外の場合は -1 を返す
    if (index >= n) {
        return -1;
    }
    int count = 0;
    // ターゲットの次の要素から末尾まで走査
    for (int i = index + 1; i < n; i++) {
        if (arr[index] < arr[i]) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int n = 8, index = 1;
    cout << getNextGreaterElementsCount(arr, n, index) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

6

この場合、ターゲットはインデックス 1 の要素 2 であり、その右側にある 3、4、5、6、7、8 の 6 つの要素がすべて 2 より大きいため、結果は 6 になります。

計算量について

この解法では、配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリを使用しないため空間計算量は O(1) となります。単一のクエリに対しては非常に効率的ですが、同じ配列に対して多数のクエリを処理する必要がある場合は、セグメントツリーなどのデータ構造を活用することでさらに最適化できます。