当前位置：首页 > ai >正文

每日一题：H指数

ai 2025/7/19 4:20:13

继续给大家带来每日一题

题目描述

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数是指他（她）至少发表了 h 篇论文，并且至少有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数是其中最大的那个。

题目示例

在这里插入图片描述

这道题目读起来可能有些拗口，我给大家翻译翻译，题目的核心就是找一个最大值h，使其能够满足

h<=数组大小
数组里大于等于h的元素个数m，要求m>=h

如下图所示：
在这里插入图片描述

无论什么思路，其核心就是找上面的两个关系：

1.h<=数组大小，所以我们最简单粗暴的思路就是从h=1开始统计，直到h=n（数组大小，也就是题目中的论文个数）

2.数组里大于等于h的元素个数m，要求m>=h 这种才是有效的h

以题目中的case为例：

citations=3, 0, 6, 1, 5

h=1，满足大于等于1的数字有：3，6，1，5
h=2，满足大于等于2的数字有：3,6,5
h=3，满足大于等于3的数字有：3,6,5
h=4，满足大于等于4的数字有：6,5
h=5，满足大于等于5的数字有：6,5
h=6,满足大于等于6的数字有6

下面我们接着去找符合满足的数量要大于h

h=1，满足的论文数：4 4>=1符合
h=2，满足的论文数：3 3>=2符合
h=3，满足的论文数 3 3>=3符合
h=4，满足的论文数 2 2>=4 不符合
h=5，满足的论文数 2 2>=5 不符合
h=6，满足的论文数 1 1>=6 不符合

所以取符合的最大h h=3
然后我们接着来看代码实现：
最暴力的解法是：直接按照我们上面的思路来

    public static int hIndex(int[] citations) {int n = citations.length;Map<Integer, Integer> indexMap = new HashMap<>();for (int i = 1; i <= n; i++) {for (int j : citations) {int count = indexMap.getOrDefault(i, 0);if (j >= i) {indexMap.put(i, ++count);}}}int max = 0;for (Map.Entry<Integer, Integer> entry : indexMap.entrySet()) {int h = entry.getKey();int count = entry.getValue();if (count >= h) {max = Math.max(h, max);}}return max;}

在这里插入图片描述

我们尝试着优化一下：如：

citations=3, 0, 6, 1, 5

我们先进行排序，排序后：0 1 3 6 5
h=1 我们发现1符合的时候，后面的就不用计算累加了，因为1后面的数组均符合，所以h=1 对应的论文数：n-index(1)=5-1=4

同理h=2 h=3…均可以以这种方式计算

    public static int hIndex2(int[] citations) {int n = citations.length;Arrays.sort(citations);Map<Integer, Integer> indexMap = new HashMap<>();for (int i = 1; i <= n; i++) {for (int j = 0; j < n; j++) {if (citations[j] >= i) {indexMap.put(i, n - j);break;}}}int max = 0;for (Map.Entry<Integer, Integer> entry : indexMap.entrySet()) {int h = entry.getKey();int count = entry.getValue();if (count >= h) {max = Math.max(h, max);}}return max;}

运行时间：
在这里插入图片描述

但是上面两种方式每次都需要从头开始找，浪费了我们排序的性能带来的便利，所以我们可以用一个索引指向计算下一个h时需要从数组的哪个位置开始读取

citations=3, 0, 6, 1, 5
排序后：0 1 3 6 5

h=1,遍历到index=1的位置
h=2，直接从index=1开始遍历，index=2时找到大于等于2的论文
h=3，直接从index=2开始遍历
依此类推
在这里插入图片描述

上面的三种方式均需要我们去二次遍历map，其实我们在第一次找每个h对应的论文数量时就可以去定位到符合条件的最大h，减少了一次遍历

    public static int hIndex4(int[] citations) {int n = citations.length;Arrays.sort(citations);int j = 0;int max = 0;for (int i = 1; i <= n; i++) {while (j < n) {if (citations[j] >= i&& (n - j) >= i) {max = Math.max(max, i);break;}j++;}}return max;}