C++의 H-인덱스 II

<시간/>

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

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