ধরুন আমাদের কাছে একজন গবেষকের উদ্ধৃতির একটি অ্যারে আছে। গবেষকের এইচ-ইনডেক্স গণনা করার জন্য আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে। আমরা জানি যে এইচ-ইনডেক্স হল একটি মেট্রিক যা একজন গবেষকের কাগজপত্রের প্রভাব গণনা করতে ব্যবহৃত হয়। আনুষ্ঠানিকভাবে H-সূচককে এইভাবে সংজ্ঞায়িত করা যেতে পারে:"একজন গবেষকের সূচক h থাকে যদি তাদের N কাগজগুলির প্রতিটিতে কমপক্ষে h উদ্ধৃতি থাকে এবং অন্য N −h কাগজগুলির প্রতিটিতে h উদ্ধৃতির বেশি না থাকে।"
সুতরাং, যদি ইনপুটটি উদ্ধৃতির মত হয় =[5, 4, 1, 2, 6], তাহলে আউটপুট হবে 3, কারণ কমপক্ষে 3টি পেপারে অন্তত 3টি উদ্ধৃতি রয়েছে −4, 5, 6।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=অ্যারের আকার, n + 1 আকারের বালতি নামে একটি অ্যারে তৈরি করুন
- আমি 0 থেকে n – 1
- পরিসরে
- x :=c[i]
- যদি x>=n, তাহলে বালতি[n] 1 দ্বারা বাড়ান, অন্যথায় বালতি[x] 1 দ্বারা বাড়ান
- cnt :=0
- এর জন্য আমি 0 থেকে নিচের রেঞ্জে:
- বালতি দ্বারা cnt বাড়ান[i]
- যদি cnt>=i, তাহলে i ফেরত দিন
- রিটার্ন - 1
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(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 = {5, 4, 1, 2, 6};
cout << (ob.solve(v));
} ইনপুট
[5, 4, 1, 2, 6]
আউটপুট
3
