C++で配列内の全要素のフロア（下限値）を効率的に求める方法

この問題では、整数要素からなる配列 arr[] が与えられます。求めるのは、同じ配列内に存在する各要素のフロア（下限値）です。フロアとなる要素が見つかればその値を出力し、存在しない場合は -1 を出力します。

配列における要素のフロアとは？

配列内のある要素のフロアとは、その要素以下の値を持つ要素の中で、最も近い（最大の）要素のことを指します。

具体例で理解しよう

入力: arr[] = {3, 1, 5, 7, 8, 2}
出力: 2 -1 3 5 7 1

この例では、要素 3 のフロアは 2、要素 1 以下の要素は他に存在しないため -1、要素 5 のフロアは 3、というように各要素ごとに計算しています。

解法アプローチ

アプローチ1: 二重ループを使用する方法

最もシンプルな方法は、二重ループを使うことです。外側のループで配列の各要素を順に処理し、内側のループでその要素のフロアとなる要素を配列内から探します。ただし、この方法の計算量は O(n²) となるため、大きな配列では非効率になります。

アプローチ2: ソート済み配列と二分探索を使用する方法

より効率的なのが、追加の配列に元の配列をソートした状態で保存しておく方法です。その後、元の配列を走査しながら、二分探索（バイナリサーチ）アルゴリズムによってソート済み配列から各要素のフロアを高速に見つけます。この方法の計算量は O(n log n) に抑えられます。

実装例

以下は、本解法の動作を示す C++ プログラムです。

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

void printFloorEle(int arr[], int n){
    vector<int> sortedArr(arr, arr + n);
    sort(sortedArr.begin(), sortedArr.end());
    for (int i = 0; i < n; i++) {
        if (arr[i] == sortedArr[0]) {
            if (arr[i] == sortedArr[1])
                cout<<arr[i];
            else
                cout<<-1;
            cout<<"\t";
            continue;
        }
        auto iterator = lower_bound(sortedArr.begin(),sortedArr.end(), arr[i]);
        if (iterator != sortedArr.end() && *(iterator + 1) == arr[i])
            cout<<arr[i]<<"\t";
        else
            cout<<*(iterator - 1)<<"\t";
    }
}
int main(){
    int arr[] = { 3, 1, 5 ,7, 8, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The Floor of every element of the given array is ";
    printFloorEle(arr, n);
    return 0;
}

出力結果

The Floor of every element of the given array is 2 -1 3 5 7 1