【C++】配列内にK以上の要素がK個以上存在するような最大値Kを求める方法

この問題では、整数型の配列 arr が与えられ、「配列内に K 以上の要素が少なくとも K 個存在する」という条件を満たす最大値 K を求めるプログラムを C++ で作成します。

問題の説明

求めるのは、配列内の「K 以上の値を持つ要素」の個数が K 個以上になるような値 K のうち、最大のものです。

具体例で問題を確認しよう

入力: arr[] = {3, 5, 1, 7, 6, 6, 4, 8}

出力: 5

説明: 配列内で 5 以上の要素は「5, 6, 6, 7, 8」の 5 個存在するため、K = 5 が条件を満たします。

解決アプローチ

この問題に対するシンプルかつ効果的な解法は、まず配列を昇順にソートし、末尾（最大値）から順に走査する方法です。各要素について、その要素以降（自身を含む）の要素数 (N - i) が、その要素の値 arr[i] 以上であるかどうか、すなわち arr[i] <= (N - i) が成立するかを判定します。条件を満たした最初の要素が、求める最大値 K となります。

計算量はソートに O(N log N)、走査に O(N) となり、実装が容易で実用性の高いアプローチです。

C++ による実装例

#include <bits/stdc++.h>
using namespace std;
int CalcMaximumVal(int arr[], int N){
    sort(arr, arr + N);
    for(int i = (N - 1); i >= 0; i--){
        if(arr[i] <= (N - i))
            return arr[i];
    }
}
int main(){
    int arr[] = {4,7,2,3,8};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列に K 以上の要素が少なくとも K 個存在するような最大値 K は "<<CalcMaximumVal(arr, N);
    return 0;
}

出力結果

配列に K 以上の要素が少なくとも K 個存在するような最大値 K は 3

コードの動作解説

サンプル配列 {4, 7, 2, 3, 8} を昇順にソートすると {2, 3, 4, 7, 8} になります。末尾から順に確認すると、値 8 の時点では残り要素数が 1 個、値 7 の時点では 2 個しかないため条件を満たしません。しかし値 4 の時点では 3 個になり、さらに値 3 に到達すると「3 以上の要素」が 4 個（3, 4, 7, 8）存在することが分かり、arr[i] <= (N - i) が初めて成立します。よって答えは 3 となります。