给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，**h 指数** 是其中最大的那个。
示例 1：
1
2
3
4
| 输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
|
示例 2：
1
2
| 输入：citations = [1,3,1]
输出：1
|
提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
计数
用一个大小为len + 1的数组计算不同引用次数的论文有多少，对于引用次数超过论文发表数的情况，当作最大论文的引用次数处理，因为h指数不可能超过len
通过从后向前遍历，用total记录论文数，当total >= i （引用次数），即大于等于该引用次数的论文数大于 i ，满足条件直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int len = citations.length;
int[] count = new int[len+1];
for(int i = 0; i < len ; i++){
if(citations[i] >= len){
count[len] ++;
}else{
count[citations[i]] ++;
}
}
int total = 0;
for(int i = len; i >= 0; i--){
total += count[i];
if(total >= i ){
return i;
}
}
return 0;
}
}
|
时间复杂度：$O（n）$
空间复杂度：$O（n）$
排序
从后向前遍历
根据 H 指数的定义，如果当前 H指数为 h 并且在遍历过程中找到当前值 citations[i]>h，则说明我们找到了一篇被引用了至少 h+1次的论文，所以将现有的 h 值加 1。继续遍历直到 h 无法继续增大。最后返回 h 作为最终答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int len = citations.length;
int h = 0;
int i = len - 1;
while(i >= 0 && citations[i] > h){
h++;
i--;
}
return h;
}
}
|
时间复杂度：$O（n log n）$
二分
我们需要找到一个值 h，它是满足「有 h 篇论文的引用次数至少为 h」的最大值。小于等于 h 的所有值 x 都满足这个性质，而大于 h 的值都不满足这个性质。同时因为我们可以用较短时间（扫描一遍数组的时间复杂度为 O(n)，其中 n 为数组 citations的长度）来判断 x 是否满足这个性质
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int hIndex(int[] citations) {
int left = 0;
int right = citations.length;
int cnt = 0;
while(left < right){
int mid = (left + right + 1) >> 1;
cnt = 0;
for(int i = 0; i < citations.length; i++){
if(citations[i] >= mid){
cnt ++;
}
}
if(cnt >= mid){
left = mid;
}else{
right = mid - 1;
}
}
return left;
}
}
|
时间复杂度：$O（n log n）$