C++のH指数II

研究者の引用の配列（引用は非負の整数）があるとします。これらの番号は、降順ではない順序で並べ替えられます。研究者のh指数を計算する関数を定義する必要があります。 h指数の定義によると、「科学者は、N個の論文のh個にそれぞれ少なくともh個の引用があり、他のN −h個の論文にはそれぞれh個以下の引用がある場合に指数hを持ちます。」

したがって、入力がcitations =[0,1,4,5,6]の場合、出力は3になります。これは、研究者が5つの論文を持っていることを示しているため、0、1、4、5、6の引用があります。それぞれ。研究者は、それぞれ4回以上の引用がある3つの論文と、それぞれ4つ以下の引用がある残りの2つの論文を持っているため、h指数は3です。

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

• ans：=0、low：=0、n：=配列のサイズ、high：=n – 1

• 配列のサイズ=0の場合、0を返します

• 低<=高-

  • 中：=低+（高-低）/ 2

  • A [mid] =配列のサイズ– midの場合、A [mid]

    を返します。

  • それ以外の場合、A [mid]> n – mid、次にhigh：=mid – 1

  • それ以外の場合は低い：=中程度+ 1

• n –高– 1

  を返します

例（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