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

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

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

漫漫长路，才刚刚开始…

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

参考文章:

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

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 指数，我们可以采用以下思路：

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

分析步骤

1. 排序数组: 对引用次数数组进行非降序排序。
2. 遍历寻找 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;
}

4. 总结

通过这道题目，我们可以学习到如何处理和分析实际问题（如学术论文的引用情况），并将其抽象为计算问题。这种能力对于算法设计和数据分析都是至关重要的。要提升这方面的能力，可以多做类似将实际问题抽象和转换为编程问题的练习，并学习更多的数据结构和算法知识来优化问题的解决方案。