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 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.
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.length1 <= n <= 1050 <= citations[i] <= 1000citationsis sorted in ascending order.
Follow up: Could you solve it in logarithmic time complexity?
Binary search.
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
left, right = 0, n
while left < right:
mid = (left + right) >> 1
if citations[mid] >= n - mid:
right = mid
else:
left = mid + 1
return n - leftclass Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >>> 1;
if (citations[mid] >= n - mid) {
right = mid;
} else {
left = mid + 1;
}
}
return n - left;
}
}class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int left = 0, right = n;
while (left < right) {
int mid = left + right >> 1;
if (citations[mid] >= n - mid) {
right = mid;
} else {
left = mid + 1;
}
}
return n - left;
}
};func hIndex(citations []int) int {
n := len(citations)
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if citations[mid] >= n-mid {
right = mid
} else {
left = mid + 1
}
}
return n - left
}