Given an array of citations (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 = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 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.

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)
		if n > 0:
			citations.sort()
			citations.reverse()
			h = 0
			while h < n and citations[h] - 1 >= h:
				h += 1
			return h
		else:
			return 0


class Solution:

	def hIndex(self, citations):
		if len(citations) == 0:
			return 0
		h = [0 for i in range(len(citations) + 1)]
		for citation in citations:
			if citation >= len(citations):
				h[len(citations)] += 1
			else:
				h[citation] += 1
		i = len(citations) - 1
		while i >= 0:
			h[i] += h[i + 1]
			if h[i + 1] >= i + 1:
				return i + 1
			i -= 1
		return 0


class Solution:

	def hIndex(self, citations):
		if len(citations) == 0:
			return 0
		else:
			citations.sort()
			i = 0
			while i < len(citations):
				if citations[-i - 1] >= i + 1:
					i += 1
				else:
					break
			return i


class Solution:

	def hIndex(self, citations):
		if len(citations) == 0:
			return 0
		maxCita = -sys.maxsize - 1
		for citation in citations:
			maxCita = max(maxCita, citation)
		start = 0
		end = maxCita
		while start + 1 < end:
			mid = start + (end - start) // 2
			if self.countAtleast(mid, citations) == mid:
				return mid
			elif self.countAtleast(mid, citations) > mid:
				start = mid
			else:
				end = mid
		if self.countAtleast(end, citations) >= end:
			return end
		else:
			return start

	def countAtleast(self, cita, citations):
		count = 0
		for citation in citations:
			if citation >= cita:
				count += 1
		return count


class Solution:

	def hIndex(self, citations):
		length = len(citations)
		if length == 0:
			return 0
		citations.sort()
		for (idx, citation) in enumerate(citations):
			counts_bigger_equal_curr_citation = length - idx
			if citation >= counts_bigger_equal_curr_citation:
				return counts_bigger_equal_curr_citation
		return 0


class Solution:

	def hIndex(self, citations):
		citations = sorted(citations)
		h = 0
		for (index, c) in enumerate(citations):
			if c <= len(citations) - index:
				if c > h:
					h = c
			else:
				if len(citations) - index > h:
					h = len(citations) - index
				break
		return h


class Solution:

	def hIndex(self, citations):
		citations.sort()
		n = len(citations)
		for i in range(n):
			if citations[i] >= n - i:
				return n - i
		return 0


class Solution:

	def hIndex(self, citations):
		N = len(citations)
		cnt = [0] * (N + 1)
		for num in citations:
			if num > N:
				cnt[N] += 1
			else:
				cnt[num] += 1
		res = 0
		for i in range(N, 0, -1):
			res += cnt[i]
			if res >= i:
				return i
		return res


class Solution:

	def hIndex(self, citations):
		N = len(citations)
		citations.sort()
		for i in range(N):
			if citations[i] < N - i:
				continue
			else:
				return N - i
		return 0


class Solution:

	def hIndex(self, citations):
		if not citations:
			return 0
		sorted_ci = list(sorted(citations))
		i = 0
		while i < len(sorted_ci) and sorted_ci[len(citations) - i - 1] >= i + 1:
			i += 1
		return i


class Solution:

	def hIndex(self, citations):
		citations.sort()
		maxnum = 0
		for i in range(len(citations)):
			currH = min(citations[i], len(citations) - i)
			if currH > maxnum:
				maxnum = currH
		return maxnum