275. H-Index II
Array, Binary Search ·Problem Statement
link: LeetCode.cn LeetCode
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:
Input: citations = [0,1,3,5,6]
Output: 3
Input: citations = [1,2,100]
Output: 2
Solution Approach
The algorithm employs binary search to efficiently find the researcher’s h-index, considering the definition that the h-index is the maximum value ‘h’ such that the researcher has published at least ‘h’ papers, each cited at least ‘h’ times.
Algorithm
-
Initialize Variables: Set two pointers, l and r, to the start and end of the sorted citations array, respectively. Use these pointers to define a search range within which the h-index will be found.
-
Binary Search: Implement a binary search within the specified range. In each iteration, calculate the middle index mid and compare the number of citations at that index (citations[mid]) with the remaining number of papers (n - mid). Adjust the search range accordingly by updating l or r. Continue the binary search until the range is narrowed down to a single value.
-
Return Result: Once the binary search concludes, return the h-index by computing n - l. This reflects the maximum value ‘h’ for which the researcher has published at least ‘h’ papers, each cited at least ‘h’ times. The algorithm runs in logarithmic time due to the nature of binary search.
Implement
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
l, r = 0, n - 1
while l <= r:
mid = (l + r) // 2
if citations[mid] == n - mid:
return n - mid
if citations[mid] > n - mid:
r = mid - 1
else:
l = mid + 1
return n - l