C++で引用リストからH指数（h-index）を求めるプログラムの実装方法

研究者の論文の被引用数を表す配列が与えられ、その研究者のH指数（h-index）を計算する関数を定義することを考えます。H指数とは、研究者の論文が持つ影響力を測るための指標で、一般的に次のように定義されます。

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

具体例

たとえば入力が citations = [5, 4, 1, 2, 6] の場合、出力は 3 となります。これは「少なくとも 3 回引用されている論文が 3 本以上存在する」（4回・5回・6回引用の 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 回以上引用されている」最大の i を線形時間で見つけられます。計算量は時間・空間ともに O(n) です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(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 = {5, 4, 1, 2, 6};
    cout << (ob.solve(v));
}

入力

[5, 4, 1, 2, 6]

出力

3