LeetCode 274. H 指数
题目描述
题意分析
H 指数是最大的整数
h，使至少h篇论文的引用次数都不小于h。这里同时限制论文数量和每篇的引用次数；引用很多次的一篇论文仍然只算一篇。设论文总数为
n，答案只能在[0,n]内。对每个候选h，只需统计引用次数至少为h的论文有多少篇，再判断数量是否达到h。
解法：计数桶倒序累计
核心思路
[!blue]
建立长度为
n+1的计数桶。bucket[c]在c<n时表示引用次数恰好为c的论文数，最后的bucket[n]则表示引用次数至少为n的论文数。这样合并大引用数不会丢失判定信息：所有待判断的阈值都不超过
n，一篇引用次数大于n的论文对这些阈值全部合格，和引用次数恰好为n的论文作用相同。从
h=n向下枚举，用papers累加已经经过的桶。加入bucket[h]后，papers就等于引用次数至少为h的论文数；继续降低阈值时，只需把刚刚满足条件的那一桶加入，不必重新扫描全部论文。若
papers >= h，至少有h篇论文满足引用要求，因此h可行。倒序枚举时，更大的候选都已经检查失败，第一次可行的值就是最大 H 指数。h=0一定可行，所以总能得到答案。
解题步骤
- 令
n = citations.length，创建长度为n + 1的计数桶。- 遍历引用次数
c，把它计入bucket[min(c, n)]。- 令
papers = 0，从h = n倒序枚举到 0。- 先执行
papers += bucket[h]，再判断papers >= h；满足时立即返回h。所有引用次数为
0时，直到阈值降到0才返回；所有论文引用次数都至少为n时，第一次检查就返回n。这两个边界都由同一流程处理。
代码实现
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的计数桶。
关键点总结
[!green]
- 答案的上界由论文数量决定，因此大引用次数可以合并到最后一桶。
- 后缀桶计数表示“至少引用
h次”的篇数，恰好对应题目条件。- 倒序首次可行保证最大性，判断必须使用
papers >= h。
易错点总结
[!yellow]
- 最后一桶必须包含所有引用次数大于等于
n的论文，不能只统计恰好等于n的论文。- 判断的是“至少
h篇”，既不能写成papers > h，也不能只接受papers == h。- 要先累加当前桶再判断，否则会漏掉引用次数恰好等于阈值的论文。
- 从
0向上直接累加得到的是“引用次数不超过阈值”的数量，与所需条件相反。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 275. H 指数 II | 中等 | 原题引文已排序，可二分定位h；本题未排序时可用排序或频次桶。 |
| 1608. 特殊数组的特征值 | 简单 | 同样寻找数值与满足阈值的元素数量之间的自洽关系，本题至少h篇引用不少于h。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！