企业官网建设流程全解析

LeetCode 274. H 指数

题目理解

H 指数定义：有 h 篇论文每篇至少被引用 h 次，其余论文每篇引用不超过 h 次。求最大的 h。

解法一：排序（O(n log n)）

思路：升序排序后，从右往左看，索引 i 处右侧（含自己）共有 n - i 篇论文，每篇引用都 ≥ citations[i]。第一个满足 citations[i] >= n - i 的位置就给出了答案。

classSolution{publicinthIndex(int[]citations){Arrays.sort(citations);intn=citations.length;for(inti=0;i<n;i++){inth=n-i;// 从 i 到末尾共有 h 篇论文if(citations[i]>=h){returnh;// 第一个满足的就是最大 h}}return0;}}

示例：citations = [3,0,6,1,5] → 排序 [0,1,3,5,6]

· i=0: h=5, 0>=5 ✗
· i=1: h=4, 1>=4 ✗
· i=2: h=3, 3>=3 ✓ → 返回 3

解法二：计数排序 / 桶排序（O(n)）

思路：H 指数最大不超过论文总数 n，所以把引用数 ≥ n 的都归入桶 n，其余按引用数入桶。然后从大到小累加桶内数量 count，当 count >= i 时 i 就是答案。

classSolution{publicinthIndex(int[]citations){intn=citations.length;int[]bucket=newint[n+1];for(intc:citations){if(c>=n)bucket[n]++;// 超过 n 的合并到 nelsebucket[c]++;}intcount=0;for(inti=n;i>=0;i--){count+=bucket[i];// 引用数 >= i 的论文总数if(count>=i){returni;// 至少有 i 篇引用 >= i}}return0;}}

示例：citations = [3,0,6,1,5]，n=5

· bucket = [1,1,0,1,0,2]（下标 0~5）
· i=5: count=2, 2>=5 ✗
· i=4: count=2, 2>=4 ✗
· i=3: count=3, 3>=3 ✓ → 返回 3

复杂度对比

解法 时间复杂度 空间复杂度 备注
排序 O(n log n) O(log n) 代码简洁
计数排序 O(n) O(n) 最优，推荐

关键点

1. H 指数范围：0 ≤ h ≤ n（论文数量）。
2. 计数排序技巧：引用数可能很大，但 > n 的值对 H 指数没有区别，统一归到 bucket[n]。
3. 从右向左遍历：count 表示"引用数 ≥ i 的论文数"，一旦 count >= i，i 就是最大的 H 指数。