274. H-Index

Hint - Sort

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        // Sort the citations in descending order

        // Initialize the index variable

        // Loop through the sorted citations array
        // Check if the citation count is greater than the current index
            // Increment the index
        // Return the H-Index
    }
};

• Sort

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        sort(citations.rbegin(), citations.rend());
        int i = 0;
        while (i < citations.size() && citations[i] > i) ++i;
        return i;
    }
};

• T: $O(N \log N)$
• S: $O(1)$

Hint - HashMap

class Solution {
public:
    // Function to calculate the H-Index given a list of citation counts
    int hIndex(vector<int>& citations)
    {
        // Map to store the frequency of each citation count

        // Populate the map with citation counts and their frequencies

        // Convert the map to a vector of pairs and sort it in descending order of citation counts
        // m.rbegin() and m.rend() reverse the order of the map

        // Initialize the count of papers that have at least 'cnt' citations

        // Iterate through the sorted list of citation counts and their frequencies
        for ()
        {
            // If the current citation count is greater than the current count plus the number of papers with this citation count
            if ()
            {
                // Increase the count by the number of papers with this citation count
            }
            // If the current citation count is equal to the current count plus the number of papers with this citation count
            else if ()
            {
                // Return the current citation count as the H-Index
            }
            // If the current citation count is less than the current count plus the number of papers with this citation count
            else
            {
                // Return the maximum of the current citation count and the current count as the H-Index
            }
        }
        // If we have iterated through all the citation counts and not returned, return the count as the H-Index
    }
};

• HashMap

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        map<int, int> m;
        for (int i = 0; i < citations.size(); ++i) ++m[citations[i]];

        vector<pair<int, int>> q(m.rbegin(), m.rend());

        int cnt = 0;
        for (int i = 0; i < q.size(); ++i)
        {
            if (q[i].first > cnt + q[i].second)
            {
                cnt += q[i].second;
            }
            else if (q[i].first == cnt + q[i].second)
            {
                return q[i].first;
            }
            else
            {
                return max(q[i].first, cnt);
            }
        }
        return cnt;
    }
};

• T: $O(n)$
• S: $O(n)$