C++ में उद्धरण सूची से H-इंडेक्स खोजें - शोधकर्ता प्रभाव माप

समस्या विवरण

मान लीजिए हमारे पास एक शोधकर्ता के उद्धरणों की सरणी है। हमें शोधकर्ता के h-इंडेक्स की गणना करने के लिए एक फ़ंक्शन परिभाषित करना है। जैसा कि हम जानते हैं, h-इंडेक्स एक शोधकर्ता के पत्रों के प्रभाव की गणना के लिए उपयोग किया जाने वाला एक मीट्रिक है। औपचारिक रूप से H-इंडेक्स को इस प्रकार परिभाषित किया जा सकता है: "एक शोधकर्ता का सूचकांक h है यदि उनके N पत्रों में से h के कम से कम h उद्धरण प्रत्येक हैं, और अन्य N - h पत्रों में से प्रत्येक में h से अधिक उद्धरण नहीं हैं।"

उदाहरण के लिए, यदि इनपुट citations = [5, 4, 1, 2, 6] है, तो आउटपुट 3 होगा, क्योंकि कम से कम 3 पत्रों में कम से कम 3 उद्धरण प्रत्येक हैं - 4, 5, 6।

समाधान दृष्टिकोण

बकेट सॉर्ट (काउंटिंग सॉर्ट) का उपयोग करके O(n) समय में:

1. n := सरणी का आकार, आकार n+1 की एक सरणी bucket बनाएं
2. i को 0 से n-1 तक लूप करें:
   • x := c[i]
   • यदि x >= n, तो bucket[n] बढ़ाएं, अन्यथा bucket[x] बढ़ाएं
3. cnt := 0
4. i को n से 0 तक घटाते हुए:
   • cnt में bucket[i] जोड़ें
   • यदि cnt >= i, तो i लौटाएं
5. -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]

आउटपुट

3