Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:


Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note:

If there are several possible values for h, the maximum one is taken as the h-index.

Follow up:


       This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
       Could you solve it in logarithmic time complexity?

Difficulty: interview

Starter code:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        

Solutions:
class Solution(object):
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         n = len(citations)
         l = 0
         r = n-1
         while l <= r:
             m = (l + r) // 2
             if m == 0 and citations[m] >= n - m or  citations[m-1] < n - (m-1) and citations[m] >= n-m:
                 return n-m
             if citations[m] < n - m:
                 l = m+1
             else:
                 r = m
         return 0


class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         n = len(citations)
         l, r = 0, n - 1
         while l <= r:
             m = (l + r) // 2
             if citations[m] >= n - m:
                 r = m - 1
             else:
                 l = m + 1
         return n - r - 1

class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         c = citations
         if not c:
             return 0
         s, e  = 0, len(c) - 1
         if c[s] >= len(c):
             return len(c)
         if c[e] < 1:
             return 0
         while s < e - 1:
             m = s + int((e - s) / 2)
             if c[m] >= len(c) - m:
                 e = m
             else:
                 s = m
         return len(c) - e

class Solution:
     """
     time: O(logn)
     """
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         if not citations:
             return 0
         
         n = len(citations)
         left, right = 0, n - 1
         
         while left + 1 < right:
             mid = (left + right) // 2
             
             if citations[mid] >= n - mid:
                 right = mid
             else:
                 left = mid
         
         for mid in (left, right):
             if citations[mid] >= n - mid:
                 return n - mid
         
         return 0

class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         h = 0
         count = 0
         for c in citations[::-1]:
             if c <= count:
                 return count
             count += 1
         return count


class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         l, r, res = 0, len(citations) - 1, 0
         while l <= r:
             mid = (l + r) // 2
             if len(citations) - mid <= citations[mid]: res, r = len(citations) - mid, r - 1
             else: l = mid + 1
         return res        

class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         citations.sort(reverse=True)
         for idx in range(len(citations)):
             if idx + 1> citations[idx]:
                 return idx
         return len(citations)


class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         citations.sort()
         for i in range(len(citations)-1, -1, -1):
             if citations[i] >= len(citations)-i and (i == 0 or citations[i-1] <= len(citations)-i):
                 return len(citations)-i
         return 0

class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         
         
         # my solution......beat 95 %
         
         l = len(citations)
         if l == 0:                return 0
         if l == 1:
             if citations[0] == 0: return 0
             else:                 return 1
         if min(citations) >= l:   return l
         
         citations = citations[::-1]
         count = 0
         thres = 0
         i = 0
         while i < len(citations):
             if thres >= count:
                 thres = citations[i]
                 count += 1
                 i += 1
             else:
                 return count-1
         return count-1
         
         
         
         


class Solution:
     def hIndex(self, citations):
         """
         :type citations: List[int]
         :rtype: int
         """
         
         
         # my solution......beat 100 %
         
         l = len(citations)
         if l == 0:                return 0          # shit testcase: []
         if l == 1:
             if citations[0] == 0: return 0          # shit testcase: [0]
             else:                 return 1          # for testcase: [1], [2] or [100] etc...
         if min(citations) >= l:   return l          # for testcase: [2,3], [5,8], [3,4,5], [7,8,9,9] etc...
         
         citations = citations[::-1]
         count = 0
         thres = 0                                   # (count, thres): this author has "count" articles with citations >= thres
         i = 0
         while i < len(citations):
             if thres >= count:
                 thres = citations[i]
                 count += 1
                 i += 1
             else:
                 return count - 1
         return count - 1