C++ using unordered_map, not counting sort, one pass


  • 0
    L

    The idea is to use a map to save frequency of each citation, and maintain the H-index from 0 to i when traversing the array. Try to increase H-index by 1 when next citation is greater than current H-index and there are enough citations for the new H-index.

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            unordered_map<int, int> freq;
            int curH = 0;  // current H-index
            int cits = 0;   // number of citations >= current H-index
            for (auto c : citations) {
                if (c > curH) {               
                    if (cits - freq[curH] >= curH) {
                        // increase current H-index by 1
                        cits += 1 - freq[curH];
                        curH++;
                    }
                    else    
                        cits++;
                }
                else if (c == curH)
                    cits++;
                freq[c]++;
            }
            return curH;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.