LeetCode 274 · H 指数：排序后一条规则搞定
H 指数的定义读起来有点绕——“至少 h 篇论文被引用了至少 h 次”。但一旦把数组排个序，这条规则就变得极其直观：从高到低数，数到第几篇时引用次数不够了，h 就是几。这个"排序后逐个检查"的思路虽然不是最优的，但最好理解，面试写这个完全够用。
题目长什么样
给你一个整数数组citations，citations[i]表示研究者的第i篇论文被引用的次数。计算并返回该研究者的h 指数。
h 指数的定义：至少发表了h篇论文，且至少有h篇论文被引用次数大于等于h。如果有多种可能的值，取最大的那个。
输入：citations = [3,0,6,1,5]
输出：3
说人话就是：找一个最大的h，使得有至少h篇论文的引用次数 ≥h。
先理解 h 指数到底是什么
h 指数本质上在衡量一个研究者的"综合产出质量"——不是看单篇论文引用多高，而是看"有多少篇论文同时达到了某个引用门槛"。
citations = [3, 0, 6, 1, 5] → 5 篇论文 h = 5? 需要 5 篇 ≥ 5 次 → 6 和 5 满足，只有 2 篇，不够 h = 4? 需要 4 篇 ≥ 4 次 → 6 和 5 满足，只有 2 篇，不够 h = 3? 需要 3 篇 ≥ 3 次 → 6、5、3 满足，有 3 篇 ✓ 所以 h = 3第一反应：排序后逐个检查
把引用次数从高到低排序，然后从第一篇开始检查：第i篇（从 0 开始）的引用次数是否 ≥i+1。
为什么是i+1？因为排完序后，前i+1篇就是引用最高的i+1篇。如果第i+1高的论文引用次数都 ≥i+1，那前i+1篇的引用次数一定都 ≥i+1（因为排过序了，前面的更大）。
classSolution:defhIndex(self,citations:List[int])->int:citations.sort(reverse=True)h=0fori,cinenumerate(citations):ifc>=i+1:h=i+1else:breakreturnh跑一遍示例 1
citations = [3, 0, 6, 1, 5] 排序（降序）: [6, 5, 3, 1, 0] i=0: citations[0]=6 >= 1 ✓ → h=1 (前1篇都 ≥ 1) i=1: citations[1]=5 >= 2 ✓ → h=2 (前2篇都 ≥ 2) i=2: citations[2]=3 >= 3 ✓ → h=3 (前3篇都 ≥ 3) i=3: citations[3]=1 < 4 ✗ → 停止! 后面不可能满足了 结果: h = 3 ✓跑一遍示例 2
citations = [1, 3, 1] 排序（降序）: [3, 1, 1] i=0: citations[0]=3 >= 1 ✓ → h=1 i=1: citations[1]=1 >= 2? → 1 < 2 ✗ → 停止! 结果: h = 1 ✓为什么遇到不满足就可以直接 break？
因为排序是降序的。如果citations[i] < i+1，那citations[i+1]只会更小，也一定< i+2。所以后面都不可能满足条件了，直接 break。
| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n log n) | 排序是瓶颈 |
| 空间 | O(1) | 原地排序 |
进阶：计数排序，O(n) 时间
如果面试官追问"能不能 O(n) 时间"——可以。利用计数排序的思路。
关键观察：h 指数不可能超过论文总数n。所以引用次数大于n的，对 h 指数来说等价于n——因为 h 最大就是n。
classSolutionCounting:defhIndex(self,citations:List[int])->int:n=len(citations)counter=[0]*(n+1)forcincitations:counter[min(c,n)]+=1total=0foriinrange(n,-1,-1):total+=counter[i]iftotal>=i:returnireturn0跑一遍示例 1
citations = [3, 0, 6, 1, 5], n = 5 计数（引用次数 > 5 的归入 5）: counter = [1, 1, 0, 1, 0, 3] 含义: 引用0次→1篇, 1次→1篇, 3次→1篇, 5次及以上→3篇 从高到低累加: i=5: total=3, 3 < 5 → 继续 i=4: total=3, 3 < 4 → 继续 i=3: total=4, 4 >= 3 → 返回 3! 结果: h = 3 ✓total的含义是"引用次数 ≥ i 的论文总数"。从n往下找，第一个满足total >= i的i就是 h 指数。
| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n) | 计数 O(n) + 遍历 O(n) |
| 空间 | O(n) | counter 数组 |
两种解法放在一起看
| 解法 | 时间 | 空间 | 思路 |
|---|---|---|---|
| 排序法 | O(n log n) | O(1) | 排序后逐个检查，最直观 |
| 计数排序 | O(n) | O(n) | 引用次数计数，从高到低累加 |
面试时先写排序法，然后主动说"如果要求 O(n)，可以用计数排序"——这种递进思考是加分项。
这道题教会我什么
h 指数的本质是一个"门槛"问题
h 指数在找一个"平衡点"：论文数量和引用次数取较小值时的最大值。排序后，这个平衡点变成了"第 i 篇论文的引用次数是否还能撑住 i+1 这个门槛"——非常直观。
排序是简化问题的利器
原始数组是无序的，很难直接判断"有几篇论文引用次数 ≥ h"。但排序后，问题变成了"从前往后数，数到第几个时引用次数不够了"——从 O(n²) 的枚举退化成 O(n) 的扫描。排序虽然花了 O(n log n)，但把问题的复杂度降了一个量级。
"大于 n 的引用次数等价于 n"这个技巧
计数排序中，min(c, n)这个操作很巧妙——h 指数最大就是 n（总共只有 n 篇论文），所以引用 100 次和引用 n 次对 h 指数来说没有区别。这个"截断"思想在处理"值域很大但有效范围有限"的问题时非常有用。
完整测试代码
fromtypingimportListclassSolution:defhIndex(self,citations:List[int])->int:citations.sort(reverse=True)h=0fori,cinenumerate(citations):ifc>=i+1:h=i+1else:breakreturnhif__name__=="__main__":s=Solution()citations=[3,0,6,1,5]print(f"输入:{citations}, 输出:{s.hIndex(citations)}")citations=[1,3,1]print(f"输入:{citations}, 输出:{s.hIndex(citations)}")citations=[100]print(f"输入:{citations}, 输出:{s.hIndex(citations)}")citations=[0]print(f"输入:{citations}, 输出:{s.hIndex(citations)}")citations=[1,1,1]print(f"输入:{citations}, 输出:{s.hIndex(citations)}")citations=[4,4,0,0]print(f"输入:{citations}, 输出:{s.hIndex(citations)}")相关题目推荐：
- LeetCode 275 · H 指数 II（引用次数已排序，用二分查找优化到 O(log n)）
- LeetCode 215 · 数组中的第K个最大元素（同样是排序/计数的思路）