এক গবেষকের সাইটেশন (উদ্ধৃতি) অ্যারে দেওয়া আছে (নন-নেগেটিভ পূর্ণসংখ্যা)। এগুলো নন-ডিক্রিজিং অর্ডারে সোর্টেড আছে। গবেষকের h-ইন্ডেক্স ক্যালকুলেট করতে হবে। h-ইন্ডেক্সের ডেফিনিশন: "এক বিজ্ঞানীর ইন্ডেক্স h হলে তার N টি পেপারের মধ্যে h টির কমপক্ষে h কটা সাইটেশন আছে, আর বাকি N-h টির সর্বোচ্চ h সাইটেশন।"
উদাহরণ: citations = [0,1,4,5,6] হলে আউটপুট ৩। কারণ ৫ টি পেপার, সাইটেশন ০,১,৪,৫,৬। গবেষকের ৩ টি পেপারে কমপক্ষে ৪ সাইটেশন, বাকি ২ টিতে সর্বোচ্চ ৪ সাইটেশন, তাই h-ইন্ডেক্স ৩।
সমাধানের ধাপগুলো:
ans := 0, low := 0, n := A.size(), high := n-1- যদি
A.size() == 0, ০ ফেরত দিন। low <= highरहने পর্যন্ত:mid := low + (high - low)/2- যদি
A[mid] == A.size() - mid,A[mid]ফেরত দিন। - অন্যথায় যদি
A[mid] > n - mid,high := mid - 1 - অন্যথায়
low := mid + 1
n - high - 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]
আউটপুট
3
