LeetCode 275 H-Index II

LeetCode 275 H-Index II

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i<sup>th</sup> paper and citations is sorted in an ascending order, return compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

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

You must write an algorithm that runs in logarithmic time.

Example 1:

**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, their h-index is 3.

Example 2:

**Input:** citations = [1,2,100]
**Output:** 2

Constraints:

• n == citations.length
• 1 <= n <= 10<sup>5</sup>
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

题目大意：

一个人的学术文章有n篇分别被引用了n次及以上，那么H指数就是n

解题思路：

数组有序，论文数从小到大有序(符合引用次数的论文数从右向左递减)，引用次数由小到大排序，所以只要从右向左遍历数组，数值和索引相交的值就是所求。

解题步骤：

二分法可提高效率，用的是

注意事项：

1. 此题是寻找单一目标，所以等号可以并入任一个if statement，但循环出来后，start必须先比较，因为贪婪法，下标越向左，越容易获得更大的结果。从这一意义上看，此题接近于first_position

Python代码：

def hIndex(self, citations: List[int]) -> int:
	if citations is None or len(citations) == 0:
		return 0
	start, end = 0, len(citations) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if citations[mid] >= len(citations) - mid:
			end = mid
		else:
			start = mid
	if citations[start] >= len(citations) - start:
		return len(citations) - start
	if citations[end] >= len(citations) - end:
		return len(citations) - end
	return 0

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)。