C++의 인용 목록에서 H-Index를 찾는 프로그램

<시간/>

연구원의 인용 배열이 있다고 가정합니다. 연구원의 h-index를 계산하는 함수를 정의해야 합니다. 우리가 알고 있는 바와 같이 h-index는 연구원의 논문의 영향력을 계산하는 데 사용되는 지표입니다. 공식적으로 H-인덱스는 다음과 같이 정의할 수 있습니다. "N개의 논문 중 h개가 각각 최소 h회 인용되고 다른 N - h개의 논문이 각각 h회 이하인 경우 연구자는 인덱스 h를 가집니다."

따라서 입력이 인용 =[5, 4, 1, 2, 6]과 같으면 출력은 3이 됩니다. 3개 이상의 논문이 각각 4, 5, 6번 이상 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

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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]