问题描述
给定一个排序的整数数组，代表一个作为每篇文章的引用次数，要求在 log(n) 的时间复杂度内找出这个作者的H指数（该作者 n 篇文章中总共有 h 篇文章被引用了至少 h 次，剩下的 n - h 篇文章的引用次数不多于 h，如果 h 值有多个，取最大的那个）。题目链接：**点我**
样例输入输出
输入：[0,1,3,5,6]
输出：3
输入：[1,2,100]
输出：2
问题解法
此题跟 LeetCode-274 类似，只不过本题给出的数组是已经排序好的，同时要求时间复杂度为 log(n)。因此可以按照 LeetCode-274 的思路，在这基础上进行二分查找即可。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int hIndex(int[] citations) {
int start = 0;
int end = citations.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (citations[middle] == citations.length - middle) {
return citations.length - middle;
}
if (citations[middle] < citations.length - middle) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return citations.length - start;
}
}
|