My very simple 44ms solution, no extra space


  • 0
    F

    The Idea is, sort the array first, then iterate it; When the current value is smaller than the number of value after it, set it as cadidate h1=citations[i] (that means there is more paper get cited than the the candidate h-index , so the h-index is validated); Than move on, till we get in to a value that the number of value after it is smaller than it's value, in this situation, we set it as another candidate h2= m-i.
    Finally, we choose the maximum of h1 and h2.

    class Solution(object):
        def hIndex(self, citations):
            """
            :type citations: List[int]
            :rtype: int
            """
            
            citations=sorted(citations)
            m=len(citations)
            h=0
            for i in xrange(m):
                if citations[i]<m-1-i:
                    h=citations[i]
                elif citations[i]>=m-i:
                    h=max(h,m-i)
                    break
            return h

  • 0
    A

    What kind of sorting algorithm are you talking about which uses no extra space and runs in O(n) time? .................


  • 0
    F

    Yes, you are right, I forgot to count the sorting... For python's embeded sorting, I think it's nlogn, I will update the title, thanks..


Log in to reply
 

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