首页 > 代码库 > Leetcode H-index

Leetcode H-index

2024-08-27 06:14:11   218人阅读

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."

For example, given citations = [3, 0, 6, 1, 5], which 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, his h-index is 3.

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

 

先对citations 排序，比较citations[i] 和 n - i， 一个是引用数，一个是至少被引用了这么多次的paper的数量。 h-index应该是二者比较小的那一个。 而且如果citations[i] < n - i , 那么应该检查下一个citations[i+1]是不是满足这个条件。

 1 class Solution(object):
 2     def hIndex(self, citations):
 3         """
 4         :type citations: List[int]
 5         :rtype: int
 6         """
 7         if not citations:
 8             return 0
 9         citations.sort()
10         n = len(citations)
11         h_index = 0
12         for i in range(n):
13             cur = min(citations[i], n - i)
14             if cur > h_index:
15                 h_index = cur
16         return h_index

或者

 1 def hIndex(self, citations):
 2         """
 3         :type citations: List[int]
 4         :rtype: int
 5         """
 6         if not citations:
 7             return 0
 8         citations.sort()
 9         n = len(citations)
10         h_index = 0
11         for i in range(n):
12             if citations[i] < n - i:
13                 h_index = citations[i]
14             else:
15                 return n - i
16         return h_index

如果citations已经是排序好了的。可以使用二分法使得搜索的复杂度变成O(longN)

 1 def hIndex(self, citations):
 2         """
 3         :type citations: List[int]
 4         :rtype: int
 5         """
 6         
 7         if not citations:
 8             return 0
 9         n = len(citations)
10         left = 0
11         right = n-1
12         
13         while left <= right:
14             mid = (left + right)//2
15             if citations[mid] < n - mid:
16                 left = mid + 1
17             else:
18                 right = mid - 1
19         
20         return n - left

 L13如果不加这个等号，对于长度=1的citations list会出错。

Leetcode H-index


联系
我们