C++で研究者のh指数（H指数）を計算する方法

h指数（h-index）とは

ある研究者の論文引用回数の配列（引用数は非負の整数）が与えられます。ここで、研究者のh指数を計算する関数を定義しましょう。

h指数は次のように定義されます。

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

たとえば、入力が citations = [3, 0, 6, 1, 7] の場合、出力は 3 になります。これは研究者が5本の論文を発表しており、それぞれ3回、0回、6回、1回、7回引用されていることを意味します。3回以上引用された論文が3本あり、残りの2本はいずれも3回以下の引用にとどまっているため、h指数は3となるのです。

解法のアプローチ

この問題は、バケット（度数分布）の考え方を使うことで効率的に解けます。手順は以下の通りです。

• n := 配列のサイズ とし、サイズ n + 1 の配列 bucket を作成する

• i を 0 ～ n − 1 の範囲で繰り返す

  • x := c[i]

  • x ≥ n であれば bucket[n] を1増やし、そうでなければ bucket[x] を1増やす

• cnt := 0

• i を n から 0 まで逆順に繰り返す

  • cnt に bucket[i] を加算する

  • cnt ≥ i となった時点で i を返す

• ループが終わった場合は −1 を返す

引用数が n 以上の論文はすべて bucket[n] にまとめてカウントするのがポイントです。h指数が n を超えることはないため、これで正しく集計できます。上から累積カウントしていき、「i 本以上の論文が i 回以上引用されている」条件を最初に満たした値が答えになります。

この手法により、時間計算量 O(n)・空間計算量 O(n) でh指数を求められます。

C++の実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int hIndex(vector<int>& c) {
        int n = c.size();
        vector <int> bucket(n + 1);
        for(int i = 0; i < n; i++){
            int x = c[i];
            if(x >= n){
                bucket[n]++;
            } else {
                bucket[x]++;
            }
        }
        int cnt = 0;
        for(int i = n; i >= 0; i--){
            cnt += bucket[i];
            if(cnt >= i)return i;
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<int> v = {3,0,6,1,7};
    cout << (ob.hIndex(v));
}

入力

[3,0,6,1,7]

出力

3