C++-এ H-Index বের করা: উদ্ধরণের তালিকা থেকে গবেষকের H-Index গণনা

এক গবেষকের পেপারগুলোর উদ্ধরণ (citations) সংখ্যা দিয়ে একটি অ্যারে দেওয়া আছে। H-Index হলো একটি মেট্রিক যা গবেষকের প্রভাব বোঝায়। আনুষ্ঠানিকভাবে: "এক গবেষকের H-Index হলো h যদি তার Nটি পেপারের মধ্যে কমপক্ষে hটি পেপারের প্রত্যেকের কমপক্ষে hটি উদ্ধরণ থাকে, এবং বাকি N-hটি পেপারের প্রত্যেকের সর্বোচ্চ hটি উদ্ধরণ থাকে।"

উদাহরণ

ইনপুট: citations = [5, 4, 1, 2, 6]

আউটপুট: 3

ব্যাখ্যা: কমপক্ষে ৩টি পেপারের কমপক্ষে ৩টি উদ্ধরণ আছে (৪, ৫, ৬)।

সমাধানের পদ্ধতি (Bucket Sort / Counting Sort)

n = citations.size(), সাইজ n+1 এর একটি বাকেট অ্যারে bucket তৈরি করুন (ইনডেক্স = উদ্ধরণ সংখ্যা, ভ্যালু = পেপারের সংখ্যা)।
প্রতিটি উদ্ধরণ x এর জন্য:
- যদি x >= n হয়, তবে bucket[n]++ করুন (কারণ H-Index n-এর চেয়ে বড় হয় না)।
- অন্যথায় bucket[x]++ করুন।
cnt = 0 আরম্ভ করুন।
i = n থেকে 0 পর্যন্ত পিছিয়ে যান:
- cnt += bucket[i] (এখন পর্যন্ত i বা তার বেশি উদ্ধরণ সম্বলিত পেপারের সংখ্যা)।
- যদি cnt >= i হয়, তবে i রিটার্ন করুন (এটিই H-Index)।
কোনো হিট না পেলে -1 রিটার্ন করুন।

C++ কোড উদাহরণ

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

int main() {
    Solution ob;
    vector<int> v = {5, 4, 1, 2, 6};
    cout << (ob.solve(v));
    return 0;
}

ইনপুট

[5, 4, 1, 2, 6]