H-Index II 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. Các con số này được sắp xếp theo thứ tự không giảm dần. 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 =[0,1,4,5,6], 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ó 0, 1, 4, 5, 6 trích dẫn tương ứng. Vì nhà nghiên cứu có 3 bài báo với ít nhất 4 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á 4 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 -

• ans:=0, low:=0, n:=size của mảng, high:=n - 1

• nếu kích thước của mảng =0, thì trả về 0

• trong khi thấp <=cao -

  • giữa:=low + (cao - thấp) / 2

  • nếu A [mid] =kích thước của mảng - giữa, thì trả về A [giữa]

  • ngược lại khi A [mid]> n - mid, thì high:=mid - 1

  • nếu không thì thấp:=mid + 1

• return n - high - 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>& 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));
}

Đầu vào

[0,1,4,5,6]

Đầu ra

3