C++で「自分以上の要素がちょうどX個」となる要素を数える方法

問題の概要

整数からなる配列が与えられます。この記事の目的は、次の条件を満たす配列中の要素の個数を求めることです。

条件：各要素について、「その要素自身を除いた配列内の、その値以上の数値の個数」が、ちょうどその値自身と一致すること。

言い換えれば、ある要素が X であるとき、配列には X 以上の数値がちょうど X 個存在しなければなりません（ただし要素そのものは数えません）。

入力例 1

Arr[]= { 0,1,2,3,4,9,8 }

出力

条件を満たす要素の個数 : 1

解説：各要素ごとに「その値以上の要素の個数」と比較すると、次のようになります。

Arr[0]: 値 0 以上の要素は 6 個 → 6 ≠ 0 、count = 0
Arr[1]: 値 1 以上の要素は 5 個 → 5 ≠ 1 、count = 0
Arr[2]: 値 2 以上の要素は 4 個 → 4 ≠ 2 、count = 0
Arr[3]: 値 3 以上の要素は 3 個 → 3 == 3 、count = 1
Arr[4]: 値 4 以上の要素は 2 個 → 2 ≠ 4 、count = 1
Arr[5]: 値 9 以上の要素は 0 個 → 0 ≠ 9 、count = 1
Arr[6]: 値 8 以上の要素は 1 個 → 1 ≠ 8 、count = 1

「ちょうど 3 個の要素が自分以上にある」という条件を満たすのは 3 のみです（3 以上の要素は 4, 8, 9 の 3 個）。したがって答えは 1 となります。

入力例 2

Arr[]= { 1,1,1,1,1 }

出力

条件を満たす要素の個数 : 0

解説：すべての要素が同じ値のため、各要素について「自身を除いた、その値以上の要素の個数」は 4 個となり、値 1 とは一致しません。よって該当する要素は存在せず、答えは 0 です。

アルゴリズムの考え方

本プログラムで採用しているアプローチの手順は以下の通りです。

• 整数配列 Arr[] に整数を格納します。
• 整数 n には配列の長さ（要素数）を保持します。
• 関数 findcount(int arr[], int n) は、配列とそのサイズを受け取り、前述の条件を満たす要素の個数を返します。
• 変数 count は、現在注目している要素以上の値を持つ「他の要素」の個数を数えるために使います。
• 変数 ans を 0 で初期化します。これが最終的な答えのカウンタになります。
• for ループを使い、先頭要素（インデックス 0）から順に配列を走査します。
• 内側のループで再び配列全体を走査し、i != j かつ arr[j] >= arr[i] を満たす要素があれば count をインクリメントします。
• 内側のループ終了後、count と arr[i] を比較します。count == arr[i]（ちょうど arr[i] 個の要素が arr[i] 以上）であれば、答え ans をインクリメントします。
• 両方のループが終了したら、ans に格納された結果を返します。

C++ 実装例

#include <iostream>
using namespace std;

int findcount(int arr[], int n){
    int count = 0;
    int ans = 0;
    for(int i = 0; i < n; i++){
        count = 0;
        for(int j = 0; j < n; j++){
            if(arr[j] >= arr[i] && i != j)
                count++;
        }
        if(count == arr[i])
            ans++;
    }
    return ans;
}

int main(){
    int Arr[] = { 0,1,2,3,4,9,8 };
    int n = sizeof(Arr) / sizeof(Arr[0]);
    cout << "条件を満たす要素の個数 : " << findcount(Arr, n);
    return 0;
}

なお、この手法では全ペア比較によって個数を数えるため、元コードにあった sort() や未使用の変数は結果に影響しないため削除しています。ロジック自体はまったく同じです。

出力

条件を満たす要素の個数 : 1

計算量について

このアプローチでは外側と内側のループで配列を二重に走査するため、時間計算量は O(n²)、追加のメモリ使用量は O(1) です。配列をソートして二分探索（upper_bound）を組み合わせれば、より効率的な実装も可能ですが、まずはこのシンプルな全比較方式でロジックを理解するのがおすすめです。