C++で配列内の各要素より大きい最も近い値を検索する方法

この記事では、配列内の各要素に対して「それより大きい値のうち最も近い値」を求める方法を解説します。ある要素 x より大きな値が配列内に存在する場合、その中で最小のものが答えとなります。存在しない場合は -1 を返します。

例として、配列が [10, 5, 11, 6, 20, 12] の場合、結果は [11, 6, 12, 10, -1, 20] になります。20 より大きな値は配列内に存在しないため、-1 を出力します。

解決アプローチ

この問題は、C++ STL の set を使うことで効率的に解けます。set は平衡二分探索木を基に実装されており、常に要素をソートされた状態で保持します。メンバ関数 upper_bound() を使えば、指定した値より大きい最小の要素（次に大きい要素）を O(log n) の時間計算量で取得できます。

サンプルコード

#include<iostream>
#include<set>
using namespace std;
void nearestGreatest(int arr[], int n) {
    set<int> tempSet;
    for (int i = 0; i < n; i++)
        tempSet.insert(arr[i]);
    for (int i = 0; i < n; i++) {
        auto next_greater = tempSet.upper_bound(arr[i]);
        if (next_greater == tempSet.end())
            cout << -1 << " ";
        else
            cout << *next_greater << " ";
    }
}
int main() {
    int arr[] = {10, 5, 11, 6, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    nearestGreatest(arr, n);
}

実行結果

11 6 12 10 -1 20

まとめ

まずすべての要素を set に挿入し、その後各要素に対して upper_bound() を呼び出すことで、次に大きい要素を求めています。全体の時間計算量は O(n log n) となり、要素数が多い場合でも高速に動作する実用的な手法です。