4ms using binary search O(nlog(max))


  • 0
    Y
    class Solution {
    public:
        int bsearch(const vector<int>& citations, int minVal, int maxVal)
        {
            //cout<<minVal << ' '<<maxVal;
            if(minVal > maxVal)     return -1;
            int mid = (minVal + maxVal)/2;
            int count = 0;
            for(int i = 0; i < citations.size(); i++)
            {
                if(citations[i] >= mid) count++;
            }
            if(count < mid) 
            {
                return bsearch(citations, minVal, mid-1);
            }
            else  
            {
                int retval =  bsearch(citations, mid+1, maxVal);
                return retval == -1? mid:retval;
            }
        }
        int hIndex(vector<int>& citations) {
            if(citations.size() == 0)
            {
                return 0;
            }
            int maxVal = INT_MIN;
            for(int i = 0; i < citations.size(); i++)
            {
                maxVal = max(maxVal, citations[i]);
            }
            return bsearch(citations, 0, maxVal);
        }
    };

Log in to reply
 

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