C++の引用リストからH指数を見つけるプログラム

研究者の引用がたくさんあるとします。研究者のh指数を計算する関数を定義する必要があります。私たちが知っているように、h指数は研究者の論文の影響を計算するために使用される測定基準です。正式には、H指数は次のように定義できます。「研究者は、N個の論文のh個にそれぞれ少なくともh個の引用があり、他のN −h個の論文にはそれぞれh個以下の引用がある場合に指数hを持ちます。」

したがって、入力がcitations =[5、4、1、2、6]のようである場合、少なくとも3つの論文にはそれぞれ少なくとも3つの引用があるため、出力は3になります。

これを解決するには、次の手順に従います-

• n：=配列のサイズ、サイズn+1のバケットと呼ばれる1つの配列を作成します
• 0からn–1の範囲のiの場合
  • x：=c [i]
  • x> =nの場合は、bucket [n]を1増やし、それ以外の場合は、bucket[x]を1増やします
• cnt：=0
• nから0までの範囲のiの場合：
  • バケットごとにcntを増やす[i]
  • cnt> =iの場合、iを返します
• 返品– 1

理解を深めるために、次の実装を見てみましょう-

例

#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