My very simple 44ms solution, no extra space

  • 0

    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
            for i in xrange(m):
                if citations[i]<m-1-i:
                elif citations[i]>=m-i:
            return h

  • 0

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

  • 0

    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.