274. 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)$

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)$