My idea is using binary search.
Suppose we have a list of citation [3,0,6,1,5]. First, sort the
citation in decreasing order --> [6,5,3,1,0]
Now it is obvious that we need to find the one whose number of citation is just >= its
index+1 (citations[i] >= i+1), and those who is after this element,
the number of citation should <= its index + 1(citations[i] < i+1).
This is because, if we look from left to right, the index+1 shows us
how many elements appears for now, and we want to find how many
elements whose number of citation > the number of those elements.
Therefore, using binary search. Reduce the size of list by comparing
citations[mid] with mid+1
def hIndex(self, citations): """ :type citations: List[int] :rtype: int """ if citations == : return 0 citations.sort(reverse = True) end = len(citations) - 1 start = 0 while start < end - 1: mid = (start + end) / 2 if citations[mid] < mid + 1: # cut the right part and remain left part end = mid elif citations[mid] == mid + 1: # just the answer return mid+1 else: # remain the right part start = mid # If only two elements left, check if all the citation>=index+1 or h-index=0 or just around the boundary if citations[end] >= end + 1: return end + 1 elif citations[start] < start + 1: return 0 else: return start + 1