H 指数
难度:
标签:
题目描述
给你一个整数数组 citations
,其中 citations[i]
表示研究者的第 i
篇论文被引用的次数。计算并返回该研究者的 h
指数。
根据维基百科上 h 指数的定义:h
代表“高引用次数” ,一名科研人员的 h
指数 是指他(她)至少发表了 h
篇论文,并且 至少 有 h
篇论文被引用次数大于等于 h
。如果 h
有多种可能的值,h
指数 是其中最大的那个。
示例 1:
输入:citations = [3,0,6,1,5]
输出:3 解释:给定数组表示研究者总共有5
篇论文,每篇论文相应的被引用了3, 0, 6, 1, 5
次。 由于研究者有3
篇论文每篇 至少 被引用了3
次,其余两篇论文每篇被引用 不多于3
次,所以她的 h 指数是3
。
示例 2:
输入:citations = [1,3,1] 输出:1
提示:
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
代码结果
运行时间: 21 ms, 内存: 16.4 MB
/*
* 题目思路:
* 1. 使用Java Stream对引用次数数组进行处理。
* 2. 先排序,然后通过遍历找出最大的 h 值。
* 3. 返回最终的 h 值。
*/
import java.util.Arrays;
public class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
return Arrays.stream(citations) // 转换为Stream
.sorted() // 对Stream中的元素进行排序
.map(i -> n - Arrays.binarySearch(citations, i)) // 映射计算h值
.filter(h -> citations[n - h] >= h) // 过滤出满足条件的h值
.max() // 找到最大值
.orElse(0); // 如果没有找到,返回0
}
}
解释
方法:
该题解的思路是先将引用次数数组按降序排序,然后从前往后遍历。对于每个位置 i,如果该位置的引用次数 citations[i] 大于等于 i+1,说明至少有 i+1 篇论文的引用次数大于等于 i+1,更新结果 res 为 i+1。最终返回 res 即为所求的 h 指数。
时间复杂度:
O(nlogn)
空间复杂度:
O(logn) 或 O(n)
代码细节讲解
🦆
请问为什么在计算h指数时需要将引用次数数组按降序排序?
▷🦆
在判断citations[i] >= i+1时,为什么使用i+1而不是直接使用i作为比较的索引?
▷🦆
如果数组中存在重复的引用次数,这种方法是否仍然有效?会不会影响最终计算出的h指数?
▷🦆
题解中没有考虑citations数组为空的情况,这样是否会在实际应用中引发错误?
▷相关问题
H 指数 II
给你一个整数数组 citations
,其中 citations[i]
表示研究者的第 i
篇论文被引用的次数,citations
已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义:h 代表“高引用次数”(high citations),一名科研人员的 h
指数是指他(她)的 (n
篇论文中)至少 有 h
篇论文分别被引用了至少 h
次。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1:
输入:citations = [0,1,3,5,6]
输出:3
解释:给定数组表示研究者总共有5
篇论文,每篇论文相应的被引用了0, 1, 3, 5, 6
次。 由于研究者有3
篇论文每篇 至少 被引用了3
次,其余两篇论文每篇被引用 不多于3
次,所以她的 h 指数是3
。
示例 2:
输入:citations = [1,2,100]
输出:2
提示:
n == citations.length
1 <= n <= 105
0 <= citations[i] <= 1000
citations
按 升序排列