LeetCode 274. H 指数
目录
题目描述
题意分析
给定每篇论文被引用的次数，求最大的 h：存在至少 h 篇论文，每篇的引用次数都不少于 h。答案是一个数，不需要指出是哪几篇论文。
约束里最强的信号是「篇数」本身：满足条件的论文最多只有 n 篇，所以 h 永远不会超过 n。这意味着引用次数里所有大于 n 的部分对判定毫无影响，一篇被引 1000 次的论文和一篇被引 n 次的论文，在任何一次「是否不少于 h」的比较中表现完全一样。
边界要单独想清楚：全是 0 时答案是 0；只有一篇论文且引用次数很大时答案是 1 而不是引用次数；数组本身无序，题目也没要求保留原顺序，但是否原地改动入参仍要心里有数。
解法：计数桶倒序累计
核心思路
H 指数是满足下面条件的最大整数 h：至少有 h 篇论文的引用次数不小于 h。它不要求恰好 h 篇，也不要求其余论文的引用次数小于 h。
若有 n 篇论文，则 h 一定在 $[0,n]$ 内。对 H 指数的判定来说，引用 n 次和引用更多次没有区别，因此可把所有大于等于 n 的引用次数合并到
bucket[n]：
bucket[i]（i < n）表示引用次数恰好为 i 的论文数；bucket[n]表示引用次数大于等于 n 的论文数。从 n 向 0 枚举 h，并累计
papers。处理完bucket[h]后保持不变量：papers等于引用次数不小于 h 的论文数。当papers >= h时，h 可行；又因为更大的候选值已经检查且均不可行，所以第一次满足条件的 h 就是答案。排序后也能从高引用区间寻找分界点，复杂度为 $O(n\log n)$；计数桶利用了 h 的有限值域，将其进一步降为 $O(n)$。
解题步骤
- 令
n = citations.length，创建长度为n + 1的计数桶。- 遍历引用次数 c，把它计入
bucket[min(c, n)]。- 令
papers = 0，从h = n倒序枚举到 0。- 先执行
papers += bucket[h]，再判断papers >= h；满足时立即返回 h。以
[3, 0, 6, 1, 5]为例，n 为 5，计数桶是[1, 1, 0, 1, 0, 2]。枚举到 h 为 5、4 时，papers都是 2，条件不成立；枚举到 h 为 3 时，papers变为 3，返回 3。h 为 4 已经失败，因此 3 不仅可行，而且最大。
代码实现
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int[] bucket = new int[n + 1];
for (int citation : citations) {
bucket[Math.min(citation, n)]++;
}
int papers = 0;
for (int h = n; h >= 0; h--) {
papers += bucket[h];
if (papers >= h) {
return h;
}
}
return 0;
}
}
func hIndex(citations []int) int {
n := len(citations)
bucket := make([]int, n+1)
for _, citation := range citations {
if citation >= n {
bucket[n]++
} else {
bucket[citation]++
}
}
papers := 0
for h := n; h >= 0; h-- {
papers += bucket[h]
if papers >= h {
return h
}
}
return 0
}
复杂度分析
- 时间复杂度：$O(n)$。统计引用次数和倒序扫描各进行一次。
- 空间复杂度：$O(n)$。使用长度为
n + 1的计数桶。
关键点总结
- 定义中的关键词是「至少」和「最大」，不是引用次数的平均值或最大值。
- h 不超过论文数 n，所以可以把引用次数截断到 n，计数信息不会丢失。
- 倒序扫描时，
papers始终表示当前 h 下的合格论文数；先累计当前桶，再做判断。- 从大到小找到的第一个可行值天然最大，这同时给出了正确性证明。
易错点总结
- 把
bucket[n]只当作「引用次数恰好为 n」：更大的引用次数会丢失。例如[100]的答案应为 1。- 判断写成
papers > h：[1]在 h 为 1 时恰好有一篇合格，应使用大于等于。- 从 0 向上累计：累计量会变成「引用次数不大于 h」的论文数，与判定目标相反。
- 先判断再累加
bucket[h]：会漏掉引用次数恰好为 h 的论文。- 把 H 指数当成引用次数最大值：
[4, 4, 0, 0]的最大引用次数是 4，但只有两篇达到两次以上，答案是 2。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 275. H 指数 II | 中等 | 数组已升序，改用二分把复杂度压到对数 |