Logn C++ solution with a simple explanation


  • 0
    C

    Note that the list is sorted in ascending order. When we examine the H-index of an entry of index i we need to check whether there are at least (totalsize - i) publications with that many citations. We do that by the following check: citation >= (citations.size() - index). If that's the case then we check the earlier entry for the same condition, and if the condition is not satisfied we return the index. Rest of the cases are trivial.

    class Solution {
    public:
    
        int hIndex(vector<int>& citations) 
        {
            if(citations.size() == 0)
                return 0;
                
            if(citations.size() == 1)
            {
                if(citations[0] > 0)
                    return 1;
                else
                    return 0;
            }
    
            return (citations.size() - hIndexUtil(citations, 0, citations.size() - 1));
        }
        
        int hIndexUtil(vector<int>& citations, int startIndex, int endIndex)
        {
            int index = (startIndex + endIndex) / 2;
    
            if(index == citations.size() - 1)
            {
                if(citations[index] == 0)
                    return citations.size();
    
                return index;
            }
            int citation = citations[index];
            
            if(citation >= (citations.size() - index))
            {
                if(index > 0 && citations[index - 1] >= (citations.size() - index + 1))
                    return hIndexUtil(citations, startIndex, index - 1);
                else
                    return index;
            }
            else
            {
                return hIndexUtil(citations, index + 1, endIndex);
            }
                
        }
    };

Log in to reply
 

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