C++의 H-인덱스

연구원의 인용 배열(인용은 음이 아닌 정수)이 있다고 가정합니다. 연구원의 h-index를 계산하는 함수를 정의해야 합니다. h-index의 정의에 따르면:"N개의 논문 중 h개가 각각 최소 h회 인용되고 다른 N - h개의 논문이 각각 h회 이하인 경우 과학자는 지수 h를 가집니다."

따라서 입력이 인용 =[3,0,6,1,7]과 같으면 연구원이 5개의 논문을 가지고 있음을 나타내므로 출력은 3, 0, 6, 1, 7 인용이 있습니다. 각기. 연구원이 각각 3회 이상 인용된 3개의 논문과 각각 3회 이하로 인용된 나머지 2개의 논문을 가지고 있으므로 h-index는 3입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열의 크기, 크기가 n + 1인 버킷이라는 배열 하나를 만듭니다.
0 ~ n – 1 범위의 i에 대해
- x :=c[i]
- x>=n이면 버킷[n]을 1만큼 증가시키고 그렇지 않으면 버킷[x]을 1만큼 증가시킵니다.
cnt :=0
범위 n에서 0 −
까지의 i에 대해
- 버킷으로 cnt 증가[i]
- cnt>=i이면 i
  를 반환합니다.
반환 – 1

예시(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]