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

この記事では、配列内の各要素に対して「最も近い大きい値」を効率的に検索する方法を解説します。ある要素 x より大きい値が配列内に存在する場合、その中で最も小さい値（次に大きい要素）をその要素の答えとし、存在しない場合は -1 を出力します。

例として、配列が {10, 5, 11, 10, 20, 12} の場合、結果は {11, 10, 12, 11, -1, 20} となります。最大値の 20 より大きい要素は配列内に存在しないため、20 に対しては -1 が出力されます。

解決のアプローチ

この問題は C++ STL の set（セット）を使うと簡単に解決できます。set は二分探索木をベースに実装されており、要素は常にソートされた状態で保持されます。二分探索木では「中間順後続（inorder successor）」が必ず次に大きい要素に相当するため、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, 10, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    nearestGreatest(arr, n);
}

出力結果

11 10 12 11 -1 20

まず、すべての要素を set に挿入してソート済みの状態を作ります。その後、各要素に対して upper_bound() を呼び出すことで、その要素より大きい最小の要素を取得します。戻り値が end() イテレータと等しい場合は、それより大きい要素が存在しないことを意味するため、-1 を出力します。

このように set と upper_bound() を組み合わせることで、総当たり方式（O(n²)）で探すよりもはるかに効率的に答えを求められます。全体の計算量は、要素の挿入と検索に O(n log n)、結果の出力に O(n) となります。