Sponsored
Sponsored
Given the array is sorted, we can efficiently search for the h-index using binary search, aiming for logarithmic time complexity. The idea is to use the binary search to find the maximum h such that citations[h] ≥ h.
Time Complexity: O(log n).
Space Complexity: O(1).
1def hIndex(citations):
2 n = len(citations)
3 left, right = 0, n - 1
4 while left <= right:
5 mid = (left + right) // 2
6 if citations[mid] == n - mid:
7 return n - mid
8 elif citations[mid] < n - mid:
9 left = mid + 1
10 else:
11 right = mid - 1
12 return n - left
13
14citations = [0, 1, 3, 5, 6]
15print(hIndex(citations)) # Output: 3The Python method hIndex implements binary search, updating left and right pointers to find the h-index. It exploits Python's integer division and flexible data handling.
In this linear scan approach, we traverse the sorted citations list from beginning to end. The goal is to determine the maximum valid h-index by checking citations against their corresponding paper count.
Time Complexity: O(n).
Space Complexity: O(1).
1public classIn Java, the method performs a direct linear scan of the citations array, checking each citation against its complement from the array size to determine the h-index directly.