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

代码训练LeetCode(22)研究者H指数

news 2025/6/6 13:02:42

代码训练(22)LeetCode之研究者H指数

Author: Once Day Date: 2025年6月4日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

274. H 指数 - 力扣（LeetCode）
力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

- - 代码训练(22)LeetCode之研究者H指数
  - - 1. 原题
    - 2. 分析
    - 3. 代码实现
    - 4. 总结

1. 原题

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

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

提示：

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

示例 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

2. 分析

本题要求计算研究者的 h 指数，其中 h 指数的定义是：一位科研人员至少有 h 篇论文，每篇论文的引用次数至少也是 h 次。我们需要从给定的引用次数数组中确定这个最大的 h 值。

为了确定 h 指数，我们可以采用以下思路：

排序: 首先将引用次数数组进行排序，这样较高的引用次数会聚集在数组的后端。
遍历计算: 从数组的末尾开始向前遍历，检查当前位置的引用次数是否大于或等于当前的索引（经过适当调整），这个索引代表了“至少有多少篇论文”的数量。

分析步骤

排序数组: 对引用次数数组进行非降序排序。
遍历寻找 h 指数: 从后向前遍历排序后的数组，对每个位置 i，检查 citations[i] 是否大于或等于 len(citations) - i。如果是，更新 h 指数的最大值。

性能优化关键点

排序算法: 使用 qsort 函数，其平均时间复杂度为 O(n log n)。
一次遍历: 在排序后，只需单次遍历即可找到 h 指数，时间复杂度为 O(n)。

3. 代码实现

#include <stdio.h>
#include <stdlib.h>int compare(const void *a, const void *b) {return *(int*)a - *(int*)b;
}int hIndex(int* citations, int citationsSize) {qsort(citations, citationsSize, sizeof(int), compare);int h = 0;for (int i = 0; i < citationsSize; i++) {int currentH = citationsSize - i; // 计算当前的h值候选if (citations[i] >= currentH) {h = currentH; // 更新h值break;}}return h;
}int main() {int citations[] = {3, 0, 6, 1, 5};int citationsSize = sizeof(citations) / sizeof(citations[0]);int result = hIndex(citations, citationsSize);printf("The h-index is %d\n", result);return 0;
}