My 4 ms C++ solution with O(n) time and space complexity. No sorting


  • 0
    J
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int maxp = citations.size(),ret = 0;
            vector<int> freq(maxp+1);
            for(auto i : citations) freq[min(maxp,i)]++;
            for(int i = 0; i < maxp+1; i++)
            {
                if(maxp >= i) ret = i;
                maxp -= freq[i];
            }
            return ret;
        }
    };

Log in to reply
 

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