O(N) c++ solution


  • 0
    T
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int cnt[citations.size()], sum = 0, ans = 0;
            fill(cnt, cnt+citations.size(), 0);
            for (auto &v : citations) if (v < citations.size()) cnt[v]++;
            for (int i = 0; i < citations.size(); i++) {
                sum += cnt[i];
                if (citations.size()-sum >= i+1) ans = max(i+1, ans);
            }
            return ans;
        }
    };

  • 0
    Y
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            vector<int> countArray(citations.size()+1,0);
            for(int i=0;i<citations.size();++i)
            {
                if(citations[i]>=citations.size())
                   ++countArray[citations.size()];
                 else
                       ++countArray[citations[i]];
            }
            int ans=0;
            if(countArray[citations.size()]>=citations.size() )
            return citations.size();
            for(int j=citations.size()-1;j>=0;--j)
            {
                countArray[j]+=countArray[j+1];
                if(ans<j&&countArray[j]>=j)
                  ans=j;
            }
          
          return ans;
        }   
    };

Log in to reply
 

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