Description
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, return the researcher’s h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
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 <= 105
0 <= citations[i] <= 1000
citations is sorted in ascending order.
Solution
o ( n ) o(n) o(n) Solution
Iterate through the citations list from back to the front, every time compare the number of papers that have higher citations with the citation.
Time complexity:
o
(
n
)
o(n)
o(n)
Space complexity:
o
(
1
)
o(1)
o(1)
o ( log n ) o(\log n) o(logn) Solution
The sorted list and requirement actually give us a hint, usually it’s by binary search that we could reduce the time complexity to o ( log n ) o(\log n) o(logn)
From the above solution, we could see that when going from the biggest citation to the smallest, the citation decrease while the number of the paper increases. So the key is to find the point where citation is smaller than the number of the paper. That is, to find the rightest index of the interval that citation is smaller than the number of the papers. Since we need to find the rightest index, we could discard the right half.文章来源：https://www.toymoban.com/news/detail-486255.html
Time complexity:
o
(
log
n
)
o(\log n)
o(logn)
Space complexity:
o
(
1
)
o(1)
o(1)文章来源地址https://www.toymoban.com/news/detail-486255.html
Code
o ( n ) o(n) o(n) Solution
class Solution:
def hIndex(self, citations: List[int]) -> int:
res = 0
paper_cnt = 0
for i in range(len(citations) - 1, -1, -1):
paper_cnt += 1
res = max(res, min(paper_cnt, citations[i]))
return res
o ( log n ) o(\log n) o(logn) Solution
class Solution:
def hIndex(self, citations: List[int]) -> int:
res = 0
left, right = 0, len(citations) - 1
while left < right:
mid = (left + right + 1) >> 1
if len(citations) - mid < citations[mid]:
right = mid - 1
else:
left = mid
mid = (left + right + 1) >> 1
if mid < len(citations) - 1:
return max(min(len(citations) - mid, citations[mid]), min(len(citations) - mid - 1, citations[mid + 1]))
return min(len(citations) - mid, citations[mid])
到了这里，关于leetcode - 275. H-Index II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
