C++で解く「H指数 II」：二分探索による効率的な実装方法

ある研究者の論文被引用数の配列（非負の整数）が与えられ、その配列は降順ではない順序（非減少順）でソートされているものとします。このとき、研究者のh指数（h-index）を計算する関数を定義するのが本問題の目的です。

h指数とは？

h指数の定義は次のとおりです。

「科学者に指標hが存在するのは、N本の論文のうちh本がそれぞれ少なくともh回引用されており、残りの N − h 本の論文がそれぞれh回以下しか引用されていない場合である。」

具体例

入力が citations = [0,1,4,5,6] の場合、出力は 3 となります。

この研究者は5本の論文を持ち、それぞれ0回、1回、4回、5回、6回引用されています。「4回以上引用された論文」が3本あり、残りの2本はいずれも4回以下の引用にとどまっているため、h指数は3と判定されます。

解法のアプローチ

配列がすでにソートされているため、二分探索（バイナリサーチ）を使うことで O(log n) の計算量で効率的に求解できます。手順は以下のとおりです。

• ans := 0、low := 0、n := 配列のサイズ、high := n - 1 として初期化する。

• 配列のサイズが0の場合は、0を返す。

• low <= high の間、以下を繰り返す。

  • mid := low + (high - low) / 2 を計算する。

  • A[mid] == 配列のサイズ - mid ならば、A[mid] を返す。

  • そうでなく A[mid] > n - mid の場合は、high := mid - 1 とする。

  • それ以外の場合は、low := mid + 1 とする。

• ループ終了後、n - high - 1 を返す。

ここでのポイントは、「mid番目以降の論文数（n - mid）」と「A[mid]の被引用数」を比較することで、条件を満たす境界位置を絞り込んでいく点です。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int hIndex(vector<int>& A) {
        int ans = 0;
        int low = 0;
        int n = A.size();
        int high = n - 1;
        if(A.size() == 0) return 0;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(A[mid] == A.size() - mid){
                return A[mid];
            }
            else if(A[mid] > (n - mid)){
                high = mid - 1;
            }
            else low = mid + 1;
        }
        return n - (high + 1);
    }
};
main(){
    Solution ob;
    vector<int> v = {0,1,4,5,7};
    cout << (ob.hIndex(v));
}

入力

[0,1,4,5,6]

出力

3

まとめ

この問題では、ソート済みの被引用数配列を活かし、二分探索によってh指数を高速に求めることができます。線形探索ではO(n)かかるところを、O(log n)まで削減できるため、大規模なデータセットでも実用的に動作します。境界条件（空配列や全要素が0の場合など）にも注意して実装しましょう。