Jonna轩姐刷LeetCode的时候碰到274这道“H指数”，第一反应是：这题名字起得挺唬人，其实背后的算法一点也不神秘。它考察的无非是排序、计数、二分查找这几个基本功，但正因为基础，反而能拆出好几种完全不同的写法。这篇就用C语言把三种主流解法从头到尾捋一遍，顺便把我在写题过程中踩过的坑、想过的优化，一并记录下来，给准备刷题的读者做个参考。
这题适合两类人看：一类是刚刷LeetCode的初学者，想弄明白“H指数”到底在算什么，另一类是准备面试的开发者，需要掌握这道题在不同限制条件下该选哪种解法。题目本身不难，但它的变体和优化思路在面试里出现频率挺高，值得认真拆解。
1. 题目到底在问什么：把"H指数"这个定义翻译成代码
1.1 用一个例子把定义拆明白
LeetCode 274的原题描述很短：给定一个数组citations，其中citations[i]代表第i篇论文被引用的次数，要求返回这个学者的H指数。
H指数的学术定义是：一名学者有h篇论文，每篇至少被引用h次，这个h的最大值就是H指数。判定条件要同时满足两个“至少”：论文数量至少是h，引用次数也至少是h。
举个例子，citations = {3, 0, 6, 1, 5}。这里有5篇论文，引用次数分别是3、0、6、1、5。我们逐个试：
- 如果h=4，需要找到至少4篇引用数≥4的论文。数组里引用数≥4的只有6和5两篇，不够4篇，所以h=4不成立。
- 如果h=3，引用数≥3的是3、6、5三篇，正好够3篇条件，h=3成立。
- h=2时，引用数≥2的也是3、6、5三篇，虽然超过2篇，但题目要的是“最大的h”，所以还是取3。
答案就是3。
这个例子能看出一个关键点：H指数不是一个固定的公式，而是一个“门槛”。你把门槛定得太高，够得着的论文就少；定得太低，虽然满足但不够“大”。算法的目标就是在0到数组长度n这个区间里，找到那个能同时满足两个条件的最大整数。
1.2 隐藏在题目里的三个思维层次
这道题刷到后面会发现，它至少可以从三个层次去拆解。
第一个层次：暴力枚举。从n往下试，降到0，每试一个h就遍历一次数组，判断引用次数≥h的论文数是否≥h。最坏情况时间复杂度O(n²)，虽然能出结果，但显然不是理想做法。
第二个层次：排序后线性扫描。把引用次数从高到低排好序，从前往后数，一旦出现“当前位置的引用次数小于等于当前位置的文章数”，答案就出来了。这个思路需要理解“引用数递减、文章数递增”这两个序列相交的含义。
第三个层次：二分查找。既然h的取值范围是[0, n]，而且存在单调性，就可以用二分在区间里不断逼近答案。每猜一个mid，调用一次判定函数，统计引用数≥mid的文章有多少篇，然后根据结果调整上下界。
这三个层次刚好对应三种解法：排序加扫描、计数法、二分查找。后面逐一展开。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 三种解法的设计思路与适用场景
2.1 排序加线性扫描：最符合直觉的写法
先排序，再从大到小扫描，是大多数人拿到这道题的第一反应，也是我认为最适合作为面试首答的方案。
排序的目的是让引用次数呈现单调性。比如上面的例子排序后是{0, 1, 3, 5, 6}（升序）或{6, 5, 3, 1, 0}（降序）。如果用升序排列，我们从右往左扫：最右边是6，说明有1篇论文引用≥6；继续往左，5说明有2篇引用≥5；再往左，3说明有3篇引用≥3。当“引用值”开始小于等于“已扫描篇数”时，这个位置就是答案。
具体代码逻辑是这样：降序排列citations，定义i从0开始遍历，代表当前数到的论文数量。当citations[i] > i时，说明第i+1篇论文的引用数还能撑得起“至少i+1次引用”的条件，继续推进。一旦出现citations[i] <= i，说明再往后就算有更多论文，引用数也掉到了门槛以下，此时答案就是i。
时间复杂度O(n log n)，主要消耗在排序上。空间复杂度取决于排序算法，C语言的qsort通常原地排序，辅助空间O(log n)级别。优点是思路直观、代码短、不容易写错，适合作为面试的保底方案。
2.2 计数法：空间换时间的关键优化
计数法的灵感来自一个观察：H指数的取值范围被限制在[0, n]之间，不可能超过论文总数。既然如此，没必要把所有引用次数都排序，只需要统计“引用次数在0到n之间各有多少篇”就行。
具体做法：创建一个长度为n+1的计数数组cnt，遍历citations。如果某个引用次数c大于n，就把它截断到n，因为超过n的引用次数对答案没有额外贡献——即使引用1000次，在最多n篇论文面前，它也只能充当“引用数≥n”的一个名额。cnt[c]++记录引用次数恰好为c的论文数。
统计完以后，从大到小累加cnt数组。累加值sum表示“引用次数至少为当前i的论文总数”。当sum首次大于等于i时，i就是答案。
举个例子，citations = {3, 0, 6, 1, 5}，n=5。计数：cnt[0]=1，cnt[1]=1，cnt[3]=1，cnt[5]=2（因为6被截断到5，加上原来的5共2篇）。从i=5往下：sum从cnt[5]=2开始，2<5，继续；加上cnt[4]=0，sum=2<4；加上cnt[3]=1，sum=3≥3，答案就是3。
这种方法的时间复杂度O(n)，空间O(n)。在论文数很大、引用次数也很大的场景下，比排序快得多。面试里追问“能不能不用排序做到O(n)”时，答案就是这个。
2.3 二分查找：把"求最大h"变成"猜答案"
第三种思路是从值域上动手。H指数只会在[0, n]这个区间取值，而判断某个候选值h是否成立，规则是清晰的：统计citations中大于等于h的元素个数，若个数≥h，则h可行。
这里存在一个单调性：h越小，条件越容易满足。h=0永远成立，h=n不一定成立。所以问题的本质是在一个有序的“可行性序列”上找最后一个可行的位置，这正是二分查找的经典应用。
每次取区间中点mid，调用判定函数。如果mid可行，说明答案至少是mid，把左边界抬到mid；如果mid不可行，说明答案一定小于mid，把右边界降到mid-1。循环结束后，左边界就是答案。
相比排序法，二分的优势在于不依赖排序的稳定性，甚至在citations非常大但n较小的时候，每次判定只需要O(n)，总复杂度和排序法一样是O(n log n)。但它多了一个判定函数的编写成本，且边界处理更容易出错。常规面试中可以作为“提出多种思路”的加分项，不一定要作为首选实现。
3. C语言实现细节：从伪代码到可提交的完整代码
3.1 排序法的C语言完整实现
用C语言写这道题，第一步就绕不开qsort。LeetCode环境支持C标准库，直接包含stdlib.h，写一个比较函数即可。比较函数注意返回值：qsort的回调需要返回负数、零、正数来表示a<b、a==b、a>b。降序排列就是b-a。
c复制int cmp(const void *a, const void *b) {
return *(int*)b - *(int*)a;
}
int hIndex(int* citations, int citationsSize) {
qsort(citations, citationsSize, sizeof(int), cmp);
int i;
for (i = 0; i < citationsSize; i++) {
if (citations[i] <= i) {
break;
}
}
return i;
}
这版代码我实测过，直接能过。核心逻辑就是循环里那个判断：排序后引用次数是递减的，i表示当前已经“覆盖”了多少篇论文。只要citations[i] > i，说明当前这篇论文引用量还撑得住“i+1篇论文至少被引i+1次”的要求；一旦变成citations[i] <= i，说明当前这篇已经撑不住了，答案就是i。
需要注意一个边界：如果所有论文的引用数都大于其下标，循环会走完整个数组，最后返回citationsSize。比如citations={10, 9, 8, 7}，排序后每一项都满足citations[i] > i，循环结束后i等于4，答案正是n。这种情况是合法的，不需要额外判断。
另一个坑是空数组。citationsSize=0时，循环不执行，i=0返回，正好是h=0，符合定义。
3.2 计数法的C语言实现要点
计数法的代码也不长，但边界条件比排序法多一层，主要在于数组长度和索引关系。
c复制int hIndex(int* citations, int citationsSize) {
if (citationsSize == 0) return 0;
int *cnt = (int*)calloc(citationsSize + 1, sizeof(int));
int i;
for (i = 0; i < citationsSize; i++) {
int c = citations[i];
if (c > citationsSize) {
cnt[citationsSize]++;
} else {
cnt[c]++;
}
}
int sum = 0;
for (i = citationsSize; i >= 0; i--) {
sum += cnt[i];
if (sum >= i) {
free(cnt);
return i;
}
}
free(cnt);
return 0;
}
这里有几个细节值得说。第一，cnt数组的长度是n+1，下标从0到n，所以cnt[n]用于存放所有“引用次数大于n”的论文。第二，用calloc而不是malloc，省得手动初始化，LeetCode环境下内存管理要自己负责，函数结束前必须free。第三，第二层循环从n往下走，sum累加的是“引用次数不小于i”的论文总数。一旦sum≥i，直接返回i；如果循环走完还没找到，说明所有论文引用都是0，返回0。
踩过的一个重要坑是误以为cnt[0]不重要。其实cnt[0]只有在i=0时才会被累加，而i=0时sum必然≥0，所以cnt[0]几乎不影响结果。但循环条件必须覆盖i=0，否则遇到零引用数组会漏掉返回0的逻辑。
3.3 二分查找的C语言代码和单调性判断
二分版本需要额外写一个判定函数，我习惯命名为enough，用来判断“是否存在至少mid篇论文的引用数不低于mid”。每次判定把整个数组遍历一遍，统计满足条件的论文个数。
c复制int enough(int* citations, int size, int mid) {
int count = 0;
for (int i = 0; i < size; i++) {
if (citations[i] >= mid) {
count++;
}
}
return count >= mid;
}
int hIndex(int* citations, int citationsSize) {
int left = 0, right = citationsSize;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (enough(citations, citationsSize, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
二分版本最容易翻车的地方是mid的取整方向。如果写成mid = left + (right - left) / 2，当left和right相邻时，比如left=3、right=4，mid会落回3，如果判定3可行，left被赋值为3，循环永远无法结束。要解决这个问题，必须用向上取整：mid = left + (right - left + 1) / 2。这是二分查找求“最后一个满足条件的位置”时的标准写法，务必记住。
这个版本的时间复杂度是O(n log n)，虽然和排序法理论同级，但实际常数更大，因为每次判定都要完整遍历。它真正的价值在于思路拓展：将来遇到需要多次对同一数组做不同阈值判断的题目，这个“判定函数+二分答案”的框架可以直接复用。
4. 常见问题、易错点与实战心得
4.1 新手最容易踩的五类坑
先说第一个常见错误：直接返回数组最大值。很多人把H指数理解成“最高的引用次数”，比如数组{3,0,6,1,5}直接返回6。这是彻底理解错了定义，H指数关心的是“够得着门槛的文章数量”，不是单篇最高引用量。排序之后如果直接返回citations[0]，一样是错的，必须通过比较下标和值来界定。
第二个错误是忽略h=0。当数组全部是0时，任何大于0的h都不成立，答案只能是0。排序法的循环自然返回0，计数法的第二层循环要确保能访问到i=0，二分法的初始左边界是0，这些都应该预先想清楚。
第三个错误是计数法中截断条件写反。有人会写if (c > n) cnt[c]++，造成数组越界。正确做法是把大于n的引用次数全部累加到cnt[n]，因为n篇论文的H指数最大就是n，超过n的引用数对答案贡献相同。
第四个错误是二分mid死循环。正如前面所说，向上取整的问题在LeetCode官方测试用例中经常触发，尤其当答案恰好在区间右端时。我自己在IDE里调试时就遇到过“运行超时”，最后发现是mid取整方向错了。
第五个错误是忽视C语言的内存管理。LeetCode的C语言接口要求你自己管理内存，排序法虽然不需要额外数组，但计数法必须注意free。我在本地测试时忘了free，在LeetCode上提交后提示内存泄漏，虽然不影响判定结果，但总归是不好的习惯。
4.2 三种解法对比与面试建议
把三种方法放在一起对比，可以更直观地看清各自的定位：
| 方法 | 时间复杂度 | 空间复杂度 | 代码量 | 核心优势 | 适合场景 |
|---|---|---|---|---|---|
| 排序+线性扫描 | O(n log n) | O(log n) | 极短 | 思路直接，不易出错 | 面试首答、快速AC |
| 计数法 | O(n) | O(n) | 较短 | 线性复杂度，不依赖排序 | 数据量大、要求O(n) |
| 二分+判定函数 | O(n log n) | O(1) | 中等 | 框架可复用，有拓展性 | 需要展示算法深度 |
面试时我会建议这样回答：先讲排序法，一句话说明“排序是为了利用单调性”，然后写出代码；如果面试官追问“能不能更快”，立刻切换到计数法，说明“H指数的范围被n限制，计数可以避免排序”；如果面试官再问“如果数组不能修改怎么办”，就可以引出二分查找，因为二分不需要排序原数组，只需要遍历统计。
这个回答路径基本覆盖了这道题所有可能的追问方向，也展现了你对同一个问题多种解法的理解层次。
4.3 从H指数延伸出去的相关题目
这道题的延伸方向很有意思。LeetCode 275题就是274的变体，区别在于题目直接给了升序数组，要求用二分查找完成，时间复杂度限制O(log n)。这正好可以把上面二分版H指数改造成更优的写法，因为数组有序，判定函数内部可以在数组上再嵌套一个二分搜索，把每次判定降到O(log n)，总复杂度就是O(log n)。
另一个延伸是“最大值最小化/最小值最大化”类题目，比如LeetCode 875“爱吃香蕉的狒狒”，就是典型的二分答案模板——猜一个速度，看时间是否达标，进而缩小区间。H指数题里的enough函数本质上就是这个判定函数。把这类模板掌握熟练以后，再遇到类似题目会轻松很多。
我刷题的时候还有一个体会：很多人上来就套二分模板，结果边界搞不清，花了大把时间。其实对H指数这道题来说，排序+扫描才是最快的解法，二分反而是“为了秀而秀”。做题要分清场景，面试也一样，先给出最合理的方案，再展示你的优化空间，而不是一上来就写最复杂的代码。
4.4 关于C语言做题的两个实用建议
如果你准备用C语言刷LeetCode，有两个细节值得提前适应。第一，qsort的比较函数返回的是int，如果直接用b-a，在处理超大整数时可能溢出，虽然LeetCode的用例一般不会触发，但习惯上写成b > a ? 1 : (b < a ? -1 : 0)更稳妥。第二，LeetCode的C语言环境默认是C17，支持stdbool.h，但很多题解接口还是老的写法，参数名、类型都以题目为准，不要想当然。
另外，平时练习可以多关注配合C语言算法学习的资源，比如翁恺老师的C语言课程和配套练习题，对指针、排序、字符串这些基本功帮助很大。PTA平台上也有一批排序和二分查找的入门题，适合在刷LeetCode热题之前先热热身。基本功扎实了，再来刷LeetCode热门100题，效率会高很多。
5. 我写完这道题之后的一点个人体会
H指数这道题本身不算难，但它是一个非常典型的“一题多解”样本：排序、计数、二分三种解法覆盖了算法面试里最常考的三种思维方向。我个人的习惯是每道题至少尝试两种解法再往下走，因为这样才能真正理解复杂度的差异在哪里。
在二分版本上我多花了一点时间，反复调试那个向上取整的问题之后，对“二分查找最后一个可行解”有了更深的体会。后来遇到LeetCode 875和275那两道题，几乎没怎么思考就能套用同样的框架。
如果你也刚开始刷LeetCode，我的建议是别急着追求“AC数量”，把每道题背后的几种解法都看懂、写一遍，比快速刷过一百道题要有用得多。特别是C语言，虽然写起来比高级语言啰嗦，但正因为它把内存、指针、排序这些底层细节暴露得很清楚，刷题带来的理解反而更深刻。这道H指数题就是个不错的练手样本，值得多花点时间琢磨。