H-Index trong C ++

Giả sử chúng ta có một mảng các trích dẫn (Các trích dẫn là số nguyên không âm) của một nhà nghiên cứu. Chúng ta phải xác định một hàm để tính chỉ số h của nhà nghiên cứu. Theo định nghĩa của chỉ số h:"Một nhà khoa học có chỉ số h nếu h trong số N bài báo của họ có ít nhất h trích dẫn mỗi bài và N - h bài báo khác có không quá h trích dẫn mỗi bài."

Vì vậy, nếu đầu vào giống như trích dẫn =[3,0,6,1,7], thì đầu ra sẽ là 3, vì nó chỉ ra rằng nhà nghiên cứu có năm bài báo, họ có 3, 0, 6, 1, 7 trích dẫn. tương ứng. Vì nhà nghiên cứu có 3 bài báo với ít nhất 3 trích dẫn mỗi bài và hai bài báo còn lại với mỗi bài không quá 3 trích dẫn, thì chỉ số h là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng, tạo một mảng được gọi là nhóm có kích thước n + 1

• cho tôi trong phạm vi từ 0 đến n - 1

  • x:=c [i]

  • nếu x> =n thì tăng nhóm [n] lên 1, nếu không thì tăng nhóm [x] lên 1

• cnt:=0

• đối với tôi trong phạm vi n xuống 0 -

  • tăng cnt theo nhóm [i]

  • nếu cnt> =i, thì trả về i

• trở lại - 1

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[3,0,6,1,7]

Đầu ra

3