Leetcode 274. H-Index

Sorting

274. H-Index

This nice visualization if from HERE.

Built-in sort

O(n log n)

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater<int>());
        for (int i = 0; i < citations.size(); ++i)
        {
            if (citations[i] < i + 1)
            {
                return i;
            }
        }
        return citations.size(); 
    }
};

Counting sort

O(n)

As the citations can be a very large number, however, the maximum h index can only be the number of papers, we can use the maximum counting number as n to solve this problem.

class Solution {
public:
    int hIndex(vector<int>& citations) {
        const int n = citations.size();
        vector<int> counter(n+1, 0);
        // counting sort. A trick to apply is the maximum h index can only be n where n is the length of citation.
        for (auto& c : citations)
        {
            if (c > n) counter[n]++;
            else counter[c]++;
        }
        int ret = 0;
        int j = n;
        // O(n) to traverse the sorted citations.
        for (int i = n; i > 0; --i)
        {
            while (counter[j] == 0) j--;
            counter[j] -= 1;
            if (j == 0 or j < ret + 1) return ret;
            else ret++;
        }
        return n;
    }
};

Thanks for reading.