C语言解LeetCode 274 H指数：三种解法详解与易错点分析

单纯看“H 指数”这四个字，很多人会误以为是什么论文影响因子、期刊分区之类的复杂指标，其实它就是一道经典的逻辑题，也是 LeetCode 上标记为中等难度的第 274 题。这道题之所以值得单独拿出来写一篇 C 语言详解，是因为它表面上是一道数组处理题，实际考察的是你对“排序后如何利用有序性”、“桶计数如何压缩状态”以及“二分查找如何选边界”这三层能力的综合运用。对正在刷题的 C 语言学习者来说，这道题是打通“会做题”到“会选解法”之间那层窗户纸的很好素材。

先说结论：这题可以用三种思路解，排序后线性扫描最直观，计数法能做到 O(n) 时间复杂度，二分查找则是锻炼模板熟练度的绝佳练习。我会把三种解法从推导到代码一步步拆开讲，顺便把 C 语言实现里那些容易翻车的细节全部指出来——比如 qsort 比较函数怎么写才安全、计数数组为什么必须开 n+1 个位置、二分死循环怎么通过取整方向来规避。无论你是刚开始刷题的新手，还是想巩固基础的老手，这篇都能给你点实在的东西。

1. 先读懂题目：H 指数到底在算什么

1.1 定义拆解与题目本质

LeetCode 274 的题目描述很简短：给你一个整数数组 citations，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，你要计算这个研究者的 h 指数。

h 指数定义：一名科研人员的 h 指数是指他（她）的 N 篇论文中 总共有 h 篇论文分别被引用了至少 h 次，且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。

这个定义看着绕，我用一句话翻译一下：一个人的 H 指数，就是“他有多少篇拿得出手的论文”和“这些论文够不够拿得出手”两个条件同时满足的最大值。举个例子，h=5 表示他有 5 篇论文被引用了至少 5 次，而且剩下那几篇引用数都低于 5。

题目本质上是在问：在一个无序的整数数组里，找一个最大的整数 h，使得数组中“大于等于 h 的元素个数”至少为 h 个。

这个表述方式有个很关键的数学性质：h 的取值范围被限制在 [0, n] 之间。理由很简单，数组一共只有 n 篇论文，不可能有超过 n 篇论文满足“引用次数至少为 h”，所以答案不可能超过 n。这就让很多解法有了优化的空间——计数法可以开一个大小为 n+1 的桶，二分查找也只需要在 [0, n] 这个区间内搜索。

1.2 三种解法的切入点差异

面对这道题，不同思维习惯的人会走完全不同的路：

• 排序法：先把数组排好序，破坏无序性之后，从大往小数，数到第 h 个元素时发现它的引用次数已经不够格了，就停止。这是最贴近人类直觉的思路，也是大多数人的第一反应。

• 计数法：既然 h 最大只有 n，我们可以把引用次数分桶统计。引用次数超过 n 的论文一率丢进“第 n 桶”，因为它们的引用次数对 h 的判断来说已经“溢出”了。然后从高到低累加桶里的论文数量，第一个满足条件的桶下标就是答案。

• 二分查找：换个角度想，答案 h 一定落在 [0, n] 区间内，而且“至少有 h 篇论文引用次数 ≥ h”这个条件存在单调性——h 越大越难满足。既然单调，就能二分。每次猜一个 mid，统计一下到底有几篇论文引用次数 ≥ mid，然后根据结果收紧区间。

这三种解法不是互相替代的关系，而是同一种逻辑在不同复杂度下的体现。我建议你把三种都写一遍，尤其是二分查找，这是所有刷题人必须滚瓜烂熟的模板之一。

2. 解法一：排序后从后往前数——最直观的 O(n log n) 方案

2.1 排序法的核心推导与关键等号

排序法有个非常简洁的实现方式。先把 citations 数组从小到大排序，然后用一个变量 h 从 0 开始，从数组末尾往前遍历，只要遇到 citations[i] > h 就把 h 加 1，遇到不满足的就直接退出循环。最后返回 h。

为什么这个写法是对的？关键在于排序后数组的有序性。我们用一个例子走一遍：citations = [3, 0, 6, 1, 5]，这是题目自带的经典样例，正确答案是 3。先排序得到 [0, 1, 3, 5, 6]：

最后 h=3，正确。

这里最容易被忽略的细节是：判断条件必须是 citations[i] > h，而不是 >=。我见过很多人在这里写错，因为直觉上“引用次数等于 h”好像也说得通。但实际上，当我们从后往前数时，h 既表示已找到的论文数量，也表示下一个要挑战的阈值。如果此刻 h=2，说明已经找到了 2 篇引用次数至少为 2 的论文；现在看到一篇引用次数正好是 2 的论文，它能算进“至少有 3 篇论文引用次数至少为 3”里去吗？显然不能，因为这篇论文的引用次数只有 2，达不到 3。所以必须用严格大于。

2.2 完整 C 语言代码与 qsort 注意事项

完整代码如下：

c复制int cmp(const void *a, const void *b) {
    return (*(int *)a > *(int *)b) - (*(int *)a < *(int *)b);
}

int hIndex(int *citations, int citationsSize) {
    qsort(citations, citationsSize, sizeof(int), cmp);

    int h = 0;
    for (int i = citationsSize - 1; i >= 0; i--) {
        if (citations[i] > h) {
            h++;
        } else {
            break;
        }
    }
    return h;
}

这里 qsort 比较函数的写法值得单独说两句。C 语言的 qsort 函数不知道元素类型，所有比较都靠一个返回 int 的函数，所以函数签名固定是 int (*compar)(const void *, const void *)。我在现场写过很多次 return *(int *)a - *(int *)b; 这种写法——在本题中 citations 元素的取值范围是 [0, 1000]，所以不会溢出，也能通过 LeetCode 的测试。但在工程实践中，如果数组中存在 INT_MAX 这样的极端值，a - b 可能溢出导致排序结果错乱。稳妥的写法是上面代码里的 (a > b) - (a < b)，它永远不会溢出，本质上就是三值比较的数学化写法。

2.3 复杂度分析与适用场景

排序法的时间复杂度是 O(n log n)，由 qsort 决定，空间复杂度 O(1)（不考虑 qsort 内部的栈开销）。这个解法最大的优点是思路简单、代码量少，面试时如果时间紧张，写出这个版本完全足够，因为它已经是这类题的“标准答案”了。缺点是当 n 特别大时排序开销明显，比如 n 达到百万级别后 O(n log n) 和 O(n) 的差距就拉开了。

从实操角度看，排序法还有一个隐藏优势：它不需要额外分配内存，不存在内存管理问题，因此很多人在 LeetCode 上提交的第一个通过版本就是它。我个人的建议是，这道题至少要能一次写对排序法，因为它能检验你两个基本功：qsort 的用法和排序后利用有序性的意识。

3. 解法二：计数法——用空间换时间把复杂度压到 O(n)

3.1 核心观察：h 不超过 n，所以引用次数可以“截断”

计数法的出发点是前面提到的那条关键性质：h 不可能超过论文总数 n。既然答案最大是 n，那么一篇论文的引用次数如果超过 n，它对计算 h 来说就和“引用次数恰好等于 n”没有区别——因为不管 h 怎么猜，最大也就猜到 n，超过 n 的引用次数在判断“是否 ≥ h”时永远成立。

基于这个观察，我们可以开一个长度为 n+1 的数组 count，其中 count[k] 表示“引用次数恰好为 k 的论文篇数”，k = 0, 1, ..., n-1，而 count[n] 专门用来装所有引用次数大于等于 n 的论文。这样一来，整个数组的引用次数分布就被压缩成了 n+1 个桶，后续统计变得非常快。

这一步常常有人想不明白：为什么不直接统计每个具体引用次数出现的频率？因为引用次数没有上限，如果直接按最大引用次数开数组，空间开销无法预估，可能开出一个巨大的数组。而按 n 截断之后，桶的数量被牢牢限制在 n+1，这就是“空间换时间”里空间可预测的关键。

3.2 从高到低累加：为什么 total >= i 时返回 i

桶建好之后，接下来就是最精彩的判断环节。我们从 i = n 开始往下遍历，同时用一个变量 total 累加 count[i]。这里的 total 含义是：引用次数至少为 i 的论文总篇数。每往下走一个 i，就把当前桶里的论文数加进 total，然后判断 total >= i。

为什么 total >= i 成立时，i 就是答案？

• total 等于引用次数至少为 i 的论文篇数，所以至少有那么多的论文满足“引用次数 ≥ i”；
• 其余的 n - total 篇论文引用次数一定小于 i，也就是不超过 i；
• 这不恰好就是 h 指数的定义吗？只不过这里 h = i。

而由于我们是从 n 往 0 方向搜索，第一次遇到的满足条件的 i 必然是最大的可行值，因此直接返回 i 即可。

整个搜索过程中还有一个天然保障：当 i 递减到 0 时，total 已经累加了全部 n 篇论文，total = n >= 0 必然成立。所以循环一定会在某个位置停下，函数一定有返回值，不需要额外处理“找不到答案”的情况。

以 [3, 0, 6, 1, 5] 为例，n=5。先统计桶：

• count[0] = 1（论文引用 0）
• count[1] = 1（论文引用 1）
• count[2] = 0
• count[3] = 1（论文引用 3）
• count[4] = 0
• count[5] = 2（论文引用 5 和 6，因为 6 ≥ 5 被塞进 5 号桶）

从 i=5 开始累加：

返回 3。

3.3 完整代码与内存管理细节

完整的计数法实现如下：

c复制int hIndex(int *citations, int citationsSize) {
    // 用 calloc 而不是 malloc，因为它会清零
    int *count = (int *)calloc(citationsSize + 1, sizeof(int));

    // 分桶统计
    for (int i = 0; i < citationsSize; i++) {
        if (citations[i] >= citationsSize) {
            count[citationsSize]++;  // 引用次数超过 n 的统统计入 n 桶
        } else {
            count[citations[i]]++;
        }
    }

    int total = 0;
    for (int i = citationsSize; i >= 0; i--) {
        total += count[i];
        if (total >= i) {
            free(count);
            return i;
        }
    }

    free(count);
    return 0;  // 实际不会走到这，但写上是好习惯
}

这里有两个容易出错的点。第一，数组大小必须是 citationsSize + 1 而不是 citationsSize，因为下标要访问到 citationsSize 这个桶。如果你开成 n 大小，当 citations[i] == citationsSize 时就会越界写入，直接踩内存。第二，调用 calloc 而不是 malloc，是因为 malloc 分配的内存内容不确定，而 calloc 会把每个字节清零；如果你用 malloc 然后忘了清零，count 数组里全是垃圾值，统计直接废掉。当然你也可以 malloc 之后手动 memset，但既然 calloc 一行就能搞定，没必要自找麻烦。

LeetCode 的判题环境其实不太计较你是否 free 内存，因为每次运行进程结束就回收了。但作为 C 语言学习者，我建议平时就养成配对释放的习惯——写个清晰的解法都做不到变量对应释放，以后写结构体链表之类的代码会很痛苦。

3.4 计数法的适用场景与思维价值

计数法把时间复杂度从 O(n log n) 降到 O(n)，空间复杂度 O(n)，对于 n 很大的场景有明显优势。但是它的缺点也很明显：你需要理解“截断”思想，也就是引用次数超过 n 后信息不再重要这件事。这个思想在很多题里都能复用。比如 LeetCode 第 41 题“缺失的第一个正数”，本质上就利用了“只关心 [1, n] 范围内的值，超出范围的直接忽略”这个截断思路。所以这道题不要觉得“计数法就是开个桶”，它的思维内核比桶本身值钱得多。

4. 解法三：二分查找——换个角度“猜”答案

4.1 为什么这道题适合二分

如果你已经把排序法和计数法都写明白了，接下来值得试试二分查找。二分查找的前提是存在单调性，而这题恰好完美的满足。

定义一个判定函数 check(x)：是否存在至少 x 篇论文引用次数 ≥ x。换个角度理解，如果我们把“搜索的答案 h”从 0 一直试到 n，会得到一个 true/false 的序列。你可能会怀疑这个序列不是单调的，比如有时候 x=3 成立，但 x=4 成立而 x=5 不成立？这不可能。假设至少有 5 篇论文引用次数 ≥ 5，那么这 5 篇同时也必然 ≥ 4，所以至少有 ≥ 4 篇成立。同理，如果至少有 4 篇论文引用 ≥ 4，其中任意一部分也必然 ≥ 3。

用数学点的话说：如果 check(x) 为真，则对所有 y < x，check(y) 也必然为真。因为满足“引用次数 ≥ x”的论文，一定也满足“引用次数 ≥ y”（当 y < x）。所以 check 函数的结果排列起来是若干个 true 后跟着若干个 false，这个序列具备二分条件，我们只需要找到最后一个 true 的位置。

4.2 二分边界的经典坑：死循环的根源

二叉查找写起来容易死在边界上。本题取值区间是 [0, n]（包括两端），我们要找的是区间内最大的满足 check 为 true 的位置。这里我给你一个经过大量题验证的模板：

c复制int left = 0, right = n;
while (left < right) {
    int mid = left + (right - left + 1) / 2;  // 关键：上取整
    if (check(mid)) {
        left = mid;         // mid 是可行的，保留它，向右搜
    } else {
        right = mid - 1;    // mid 不可行，向左缩
    }
}
return left;

这个模板的灵魂是 (right - left + 1) / 2 也就是上取整。为什么要上取整？你可以设想一个最危险的情况：left = 3, right = 4，此时下取整 mid = 3 + (4 - 3) / 2 = 3。如果 check(3) 恰好为 true，那么执行 left = mid 后 left 仍然是 3，区间没有任何收缩，循环永远走不出去——这就是典型的二分死循环。而如果采用上取整，mid = 3 + (4 - 3 + 1) / 2 = 4，无论 check(4) 是真是假，区间都会向中间收敛一格，循环必然终止。

另外一个值得提醒的细节是：mid 的计算最好写成 left + (right - left + 1) / 2 而不是 (left + right + 1) / 2。两者在数学上等价，但前者多用一次减法和加法，可以避免 left + right 溢出。刷题时数组长度可能很大，养成防溢出的习惯能帮你少错一次。

4.3 完整代码与 check 函数实现

c复制int countGE(int *citations, int citationsSize, int threshold) {
    int cnt = 0;
    for (int i = 0; i < citationsSize; i++) {
        if (citations[i] >= threshold) {
            cnt++;
        }
    }
    return cnt;
}

int hIndex(int *citations, int citationsSize) {
    if (citationsSize == 0) return 0;

    int left = 0, right = citationsSize;

    while (left < right) {
        int mid = left + (right - left + 1) / 2;  // 上取整，配合找最后一个 true
        if (countGE(citations, citationsSize, mid) >= mid) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

这个版本的 check 函数时间开销是 O(n)，外层二分循环 O(log n)，所以总时间复杂度 O(n log n)。不少人会误解二分查找“一定比排序快”，但实际上这里的二分每次都要遍历数组，和排序法的复杂度同阶。它真正的价值在于：把题目归结为一个“搜索答案 + 验证答案”的思路框架，这套框架能解决一大类“要你求某个最大/最小值”的题目。比如 LeetCode 第 875 题“爱吃香蕉的狒狒”、第 1011 题“在 D 天内送达包裹的能力”，全都是同一个套路：确定答案范围，写 check 函数，二分查边界。

4.4 特殊输入与二分边界要不要额外处理

有一个边界值得单独提：当 citations = [0, 0, 0] 时，left=0, right=3。mid=2，countGE(2)=0，不满足，right=1；mid=1，countGE(1)=0，不满足，right=0。循环结束，返回 left=0。正确。

当 citations = [100, 100, 100] 时，mid=2（上取整 (0+4)/2=2），countGE(2)=3 >= 2，left=2；mid=3，countGE(3)=3 >= 3，left=3；mid=4，countGE(4)=0，不满足，right=3。结束，返回 3。正确。

所以这个模板不需要在循环外再补 if (left == n && check(n)) return n; 之类的处理，边界情况都被模板自然吸收了。

5. 三种方案横向对比与选型建议

把三种解法放在同一张表格里，差异一目了然：

从竞赛角度，计数法显然是最优解，因为 O(n) 是理论下界——你的输入数据至少要读一遍才能得出结果。从工程角度，如果 n 不超过 10000，排序法和二分查找在机器上的耗时差异可能只有几毫秒，完全无所谓。从学习角度，我建议三道题都写，尤其是二分查找版本的 check 函数，它在很多题里都能原封不动地复用。

实际面试时，我通常的做法是先说出排序法并给出正确代码，然后追问一句“能不能做到 O(n)”，再说计数法。这展示的不是简单的“背题”，而是对复杂度的敏感度。至于二分查找版本，如果你能在面试中主动补充并讲清楚单调性来源，会是一个很好的加分项。

6. 刷题实录：几个容易踩的坑和排查思路

6.1 排序法的两种常见翻车

第一个翻车点在比较函数。有人写成 return *(int *)a - *(int *)b，这道题数据范围小没事，但如果引用次数真的给到 INT_MAX，两个大数相减直接溢出，轻则排序错乱，重则数组越界访问直接爆数组。养成写三值比较的习惯并不难，多敲几行代码，规避掉一个隐性地雷，很划算。

第二个翻车点在遍历方向和判断符号。升序数组后往前数要用 citations[i] > h；如果改成 citations[i] >= h，上面的 [1,1,1,1] 用例会让你得到错误答案 2 而不是 1。不少人靠脑内模拟样例通过了测试，没注意这个符号的深层含义，下次换个用例就翻车。反过来，如果你选择从前往后遍历找第一个 citations[i] >= n - i 的位置然后返回 n - i，判断符号就得用 >=，倒过来又错。这两种写法的符号正好相反，本质上是同一个条件的两种表述，初学者容易搞混。

6.2 计数法的越界与释放问题

计数法最常见的运行时错误发生在数组索引越界。citations[i] 的最大值就是 citationsSize，此时必须存进 count[citationsSize]；如果你开的桶是 int count[citationsSize]，直接越界。LeetCode 对越界的报错方式不一定友好，有时候是 WA（Wrong Answer），有时候是 RunTime Error，排查起来令人头大。这类问题事前防范比事后排查更有效：开 n+1 个桶，并在分桶逻辑里用 >= 判断把溢出数据兜底进最后一格。

内存释放也值得一题。calloc 配 free 是一对，如果你是 calloc 出来的数组，在 return 之前手动 free 掉。这道题在 LeetCode 上不 free 也能过，但如果你在自己本地的容器里反复调用这个函数，不 free 就是一次内存泄漏。

6.3 二分查找的循环终止与结果验证

二分查找如果陷入死循环，绝大多数原因都是区间不收敛，也就是上取整还是下取整的选择问题。在这个“找最后一个 true”场景里，务必使用上取整。一个排查技巧是：把 mid = left + (right - left + 1) / 2 改成 mid = left + (right + left) / 2 都不行，一旦 left 和 right 相邻且 check(left) 为真，left 不会增长，程序卡死。你可以用 [0, 1] 这样的小区间做纸面推演，几秒钟就能发现问题所在。

另一个排查技巧是输出 mid 和 check(mid) 的结果。二分算法本来就过程简单，打点日志看每次迭代的 left、right、mid 变化，很快就能定位边界错误，比盯着代码干想效率高得多。

6.4 边界用例自查清单

写完代码后，建议花十秒钟跑一遍这些边界用例：

• [] 空数组：三种解法都应返回 0
• [0]：返回 0
• [0, 0, 0]：返回 0
• [1, 1, 1, 1]：返回 1
• [100, 100, 100]：返回 3（因为 n=3，最多只有 3 篇论文）
• [11, 15]：返回 2（两篇论文引用都 ≥ 2）

其中 [11, 15] 这个用例特别能检验你写得到底对不对：n=2，答案是 2。排序法从后往前数：15 > 0 得 h=1；11 > 1 得 h=2；结束。计数法：count[2]=2，从 i=2 开始 total=2 >= 2，返回 2。二分法：right=2，mid=1，countGE=2 >= 1，left=1；mid=2，countGE=2 >= 2，left=2；返回 2。三种解法在这个用例上的行为完全一致，非常适合作为快速自测。

我个人实际刷这道题的经验是：第一次用排序法通过后，隔了几天又用计数法重做了一遍，第二次果然在 count 数组大小上栽了个跟头，开了 n 大小导致越界。后来把二分查找模板也套进来练熟了，才真正做到在面试里随时可以写出任意一种。这道题刷三遍的意义不在于重复，而在于每换一种解法，你就强迫自己重新思考了一遍“h 指数的本质是什么”，这种思考比答案本身值钱得多。