05 August 2008
Given an array of citations sorted in ascending order (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.”
Example:
1
2
3
4
5
6
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, her h-index is 3.
Note:
If there are several possible values for h, the maximum one is taken as the h-index.
Follow up:
1
citations
这个题跟274比的区别是原数组是升序的，上一题使用桶排序，这个题已经排序了，那考虑二分才能得到更好的performance。
二分搜索：在升序的引用数数组中，假设数组长为len，下标为i，则len - i就是引用次数大于等于下标为i的文献所对应的引用次数的文章数（总长度 - i，注意i从0开始，第0篇文章 - 没有文章）。如果该位置的index的数值小于文章数，则说明则是有效的H指数（达到引用至少为i的文章数比i本身代表的数多），如果一个数是H指数，那最大的H指数一定在它或者它的后面（因为是升序的）。根据这点就可已进行二分搜索了。这里left = mid + 1的条件是citations[mid] < len - mid，确保退出循环时left肯定是指向一个有效的H指数。 时间 O(logN) 空间 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (citations[mid] >= len - mid) {//len - mid代表citations[mid]“应该”对应的引用数
right = mid - 1;
} else {
left = mid + 1;
}
}
return len - left;
}
}