ধরুন আমাদের কাছে একজন গবেষকের উদ্ধৃতির একটি অ্যারে (উদ্ধৃতিগুলি অ-ঋণাত্মক পূর্ণসংখ্যা) আছে৷ গবেষকের এইচ-ইনডেক্স গণনা করার জন্য আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে। h-সূচকের সংজ্ঞা অনুসারে:"একজন বিজ্ঞানীর সূচক h আছে যদি তার/তার N কাগজপত্রগুলির প্রতিটিতে কমপক্ষে h উদ্ধৃতি থাকে এবং অন্য N −h কাগজগুলির প্রতিটিতে h উদ্ধৃতির বেশি না থাকে।"
সুতরাং যদি ইনপুটটি উদ্ধৃতি =[3,0,6,1,7] এর মতো হয়, তাহলে আউটপুট হবে 3, কারণ এটি নির্দেশ করে যে গবেষকের পাঁচটি গবেষণাপত্র রয়েছে, তারা 3, 0, 6, 1, 7টি উদ্ধৃতি পেয়েছে। যথাক্রমে যেহেতু গবেষকের 3টি পেপার রয়েছে যার প্রতিটিতে কমপক্ষে 3টি উদ্ধৃতি রয়েছে এবং বাকি দুটি পেপার যার প্রতিটিতে 3টির বেশি উদ্ধৃতি নেই, তাহলে h-সূচকটি হল 3৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=অ্যারের আকার, n + 1 আকারের বালতি নামে একটি অ্যারে তৈরি করুন
-
0 থেকে n – 1
রেঞ্জের i জন্য-
x :=c[i]
-
যদি x>=n, তাহলে বালতি[n] 1 দ্বারা বাড়ান, অন্যথায় বালতি[x] 1 দ্বারা বাড়ান
-
-
cnt :=0
-
আমি n থেকে 0 −
রেঞ্জে-
বালতি দ্বারা cnt বৃদ্ধি [i]
-
যদি cnt>=i, তাহলে i
ফেরত দিন
-
-
রিটার্ন - 1
উদাহরণ(C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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)); }
ইনপুট
[3,0,6,1,7]
আউটপুট
3