O(N) C++ solution


  • 4
    L
    class Solution {
    public:
    int hIndex(vector<int>& cit) {
        vector<long> hist(cit.size()+1,0);
        for(int i=0;i<cit.size();++i)
            ++hist[min<int>(cit.size(),cit[i])];
    
        long cumSum=0;
        for(int i=hist.size()-1;i>=0;--i) {
            cumSum+=hist[i];
            if(cumSum>=i)
                return i;
        }        
        return 0;
    }
    };

Log in to reply
 

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