4ms C++ solution in O(n) complexity


  • 1
    X

    share my c++ code

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            if(citations.empty())
                return 0;
            vector<int> hist(citations.size(), 0);
            for(int cite : citations){
                if(cite >= hist.size()){
                    hist[hist.size()-1]++;
                }
                else if(cite > 0){
                    hist[cite-1]++;
                }
            }
            int cur = hist[hist.size()-1];
            for(int i = hist.size()-2; i >= 0 ;i--){
                hist[i] += cur;
                cur = hist[i];
            }
            for(int i = hist.size()-1 ; i >= 0 ; i--){
                if(hist[i] >= i+1){
                    return i+1;
                }
            }
            return 0;
        }
    };

Log in to reply
 

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