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?

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

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

Solutions:
class Solution(object):

	def hIndex(self, citations):
		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):
		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:

	def hIndex(self, citations):
		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):
		h = 0
		count = 0
		for c in citations[::-1]:
			if c <= count:
				return count
			count += 1
		return count


class Solution:

	def hIndex(self, citations):
		(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):
		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):
		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):
		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