LeetCode 274中等排序
H 指数 图解题解
这道题到底在问什么
给一个数组 citations,citations[i] 是第 i 篇论文的被引用次数。求该作者的 h 指数:满足「有 h 篇论文各被引 ≥ h 次」的最大 h。
- citations
- [3,0,6,1,5]
- 输出
- 3
- 因为
- 有 3 篇被引 ≥3 次(6、5、3)
最优解：一步一步想明白
- 3关键洞察:把引用数降序排好后,排在第 i 位(从 1 数)的论文,意味着「至少有 i 篇论文的引用 ≥ 它」。于是只要看每个位置的值够不够大就行。
- 4还没排序这是原始的 5 个引用数,顺序是乱的。要用排序法,第一件事就是把它们从大到小重新排列。下面用「每一轮挑出剩下最大的、放到最左边」来演示排序。
- 5扫描中 · 暂定 3指针停在要填的位置 0。开始扫一遍找剩余最大值,先把第一个 3 当作暂定最大。
- 6发现更大 → 6继续往右扫,3、0 都不如它,扫到下标 2 的 6——这是目前最大的,记下它。
- 7最大就是 6剩下的 1、5 也都比 6 小,扫描结束。整段最大确实是 6,接下来把它换到位置 0。
- 86 就位6 和原来位置 0 的 3 交换,位置 0 现在是 6,锁定(变灰底)。继续填位置 1。
- 9找剩余最大 → 5位置 0 已锁定。在剩下的 0、3、1、5 里找最大,是 5。准备把它换到位置 1。
- 105 就位5 和位置 1 的 0 交换,位置 1 现在是 5,锁定。前两位已经是 6、5。继续位置 2。
- 11找剩余最大 → 3在剩下的 3、1、0 里找最大,是 3,它正好已经在位置 2,不用动。锁定位置 2。
- 123 就位位置 2 锁定为 3。剩下的 1、0 本来就是从大到小,排序完成。最终降序结果:[6,5,3,1,0]。
- 13[6,5,3,1,0]排好了!现在进入第二阶段:指针从左到右走,在每个位置 i 检查 citations[i] ≥ i+1 是否成立。i+1 表示「到这一位为止,前面有多少篇论文」。
- 146 ≥ 1 ?指针到位置 0。这是第 1 篇,问:它的引用 6 是否 ≥ 1?也就是「能不能凑出 1 篇被引 ≥1 次」。
- 156 ≥ 1 成立6 ≥ 1,成立!说明「有 1 篇被引 ≥1 次」一定办得到,候选答案 h = 1。指针右移看能不能更大。
- 165 ≥ 2 ?指针到位置 1。这是第 2 篇,前 2 篇里最小的就是它(5)。问:5 是否 ≥ 2?即「能不能凑出 2 篇都被引 ≥2 次」。
- 175 ≥ 2 成立5 ≥ 2,成立!前 2 篇(6 和 5)都 ≥2 次,候选 h = 2。继续。
- 183 ≥ 3 ?指针到位置 2。这是第 3 篇,前 3 篇里最小的是 3。问:3 是否 ≥ 3?即「能不能凑出 3 篇都被引 ≥3 次」。
- 193 ≥ 3 成立3 ≥ 3,成立!注意恰好相等也算通过。前 3 篇(6、5、3)都 ≥3 次,候选 h = 3。
- 201 ≥ 4 ?指针到位置 3。这是第 4 篇,值只有 1。问:1 是否 ≥ 4?即「能不能凑出 4 篇都被引 ≥4 次」。
- 211 < 4 不成立1 < 4,失败!第 4 篇只有 1 次引用,凑不出「4 篇都 ≥4 次」。一旦失败,后面更小的更不可能,直接停。答案就是停下来前的候选 h = 3。
- 22答案 3 ✓结束。绿色的前 3 篇(6、5、3)就是支撑答案的论文——它们每篇引用都 ≥3,而第 4 篇撑不到 4。所以 h 指数 = 3。
- 23为什么扫到失败就能停?因为降序后值越往右越小、要求 i+1 却越往右越大——一边降一边升,一旦交叉(失败),后面只会更不满足,所以第一个失败点就是分界线。
- 27位置 2: 3 > 3 ?假如把条件错写成 >:走到位置 2 时 3 > 3 不成立,会提前停在 h=2,少算了一篇。正确答案 3 被漏掉——这就是等号必须保留的铁证。
⚠️ 容易写错的地方
✗ 错：条件写成 citations[i] > i+1
✓ 对：必须是 citations[i] >= i+1
恰好相等(如 3≥3)也算通过,用 > 会少算一档,h 偏小
✗ 错：求「有几篇 ≥h」时漏算等于 h 的
✓ 对：≥ 包含等于
h 指数定义是「≥ h 次」,等于 h 的论文也要计入
完整代码（Python / C++ / Java）
Python
class Solution:
def hIndex(self, citations):
citations.sort(reverse=True) # 从大到小排
h = 0
for i in range(len(citations)):
if citations[i] >= i + 1: # 第 i+1 篇够 i+1 次
h = i + 1
else:
break # 失败即停
return hC++
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.rbegin(), citations.rend()); // 降序
int h = 0;
for (int i = 0; i < (int)citations.size(); i++) {
if (citations[i] >= i + 1) h = i + 1;
else break;
}
return h;
}
};Java
import java.util.Arrays;
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations); // 升序
int n = citations.length, h = 0;
for (int i = 0; i < n; i++) {
if (citations[i] >= n - i) { // 从大端算第几篇
h = n - i;
break;
}
}
return h;
}
}复杂度
时间复杂度
O(n log n)
瓶颈在排序;排完只需一趟 O(n) 扫描
空间复杂度
O(1)
原地排序 + 几个变量(不算排序内部栈空间)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 H 指数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能做到 O(n)?+
能。用计数桶:开 n+1 个桶,引用 ≥n 的都计入第 n 桶;再从 n 往 0 累加篇数 cnt,第一个满足 cnt ≥ h 的 h 即答案。这是 LC275 之外的 O(n) 写法。
如果数组已经升序排好(LC275)呢?+
直接二分:找最小的下标 i 使 citations[i] ≥ n−i,则 h = n−i,做到 O(log n)。
h 指数的取值范围?+
0 ≤ h ≤ n(n 为论文数)。再高的单篇引用也无法让 h 超过总篇数。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 H 指数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。