企业官网建设流程全解析

力扣第274题 H 指数，是我刷“排序与计数类”题目时印象很深的一道题。题目本身很短，一句话就能说完：给你一个数组 citations，第 i 个数字代表第 i 篇论文的被引次数，让你算出这位作者的 h 指数。但真上手写代码就会发现，定义的细节特别容易错，很多人第一次提交都栽在“至少 h 篇论文分别被引用了至少 h 次”这句话上。这篇文章我会把三种主流解法全部拆开讲，从排序扫描、计数数组到二分答案，逐步给出可复现代码、复杂度分析和测试用例，再专门用一章记录我实际做题时踩过的坑和排查方法。它适合刚入门、想彻底捋清题目逻辑的读者，也适合想巩固“计数优化”和“二分答案 check 函数”两种通用思想的进阶者。

1. 题目到底在问什么：先把 H 指数定义彻底吃透

1.1 从科研圈的“代表作评价”说起

H 指数是学术圈用来快速衡量研究者论文影响力的一项指标。一个人公开发表了 n 篇论文，每篇论文都被其他人引用了一定次数，那么他的 h 指数就是最大的那个整数 h，使得“至少有 h 篇论文，每篇的被引次数都不低于 h”。

这句话绕，我建议翻译成大白话：把论文按被引次数从高到低排成一列，从第 1 篇开始往后数，看看能不能数到第 h 篇，并且第 h 篇的被引次数仍然不低于 h。换一种更直观的说法：把论文按被引次数画成柱状图，每根柱子的高度就是这篇论文的引用数，然后想象一条从原点出发的 y = x 斜线，h 指数差不多就是柱状图和这条斜线相交的最高位置。

举个例子，某作者有 5 篇论文，被引次数分别是 3、0、6、1、5。把它们从高到低排好就是 6、5、3、1、0。这时 h 只能取 3，因为前 3 篇是 6、5、3，全都大于等于 3；但第 4 篇只有 1，小于 4，所以 h 不能是 4，更不可能是 5。这个例子就是题目里给的示例，可很多初学者会把它误读成“被引次数总和除以论文数”，或者“引用数超过论文总数一半就算一篇”，这两种理解都是错的。

1.2 题目原文、数据范围与三个基础示例

题目给的是一个整数数组，citations[i] 表示第 i 篇论文被引用的次数，要求返回这位研究者的 h 指数。以下三个例子能帮我们校准理解：

• 输入 [3, 0, 6, 1, 5]，排序后是 [0, 1, 3, 5, 6]，答案是 3。
• 输入 [1, 3, 1]，答案是 1。这里特别容易看错：虽然数组里有 3 篇论文，其中 2 篇引用数大于等于 1，但 h 要取最大合法值。h = 2 时，需要至少有 2 篇论文的引用数大于等于 2，可整个数组里只有 1 篇是 3，另一篇 1 不达标，所以答案只能是 1。
• 输入 [100]，答案是 1。只有一篇论文，h 最大也不可能超过论文总数 1。

题目数据范围通常不算大，论文数量最多几千篇，引用次数是非负整数。这个范围意味着后面要讲的计数数组解法完全可行，不需要担心内存爆炸。

1.3 “至少”两个字，是整道题的分水岭

我在“至少”这两个字上栽过跟头。注意题目说的是“至少 h 篇论文被引用了至少 h 次”，这意味着两件事。

第一，一篇论文被引 100 次，在判定某个候选 h 时，它也只算“1 篇论文”，不会因为引用次数高就算成 2 篇。第二，被引次数恰好等于 h 的论文同样满足条件，“至少”是包含等于的。比如 [4, 4, 4, 4] 这个数组，答案是 4，因为 4 篇论文都大于等于 4；如果你把条件写成“严格大于 h”，就会错误地得到 0。

h 的取值也有限制：它必须是整数，不可能超过论文总数 n，也不可能小于 0。这些限制看着简单，但它们是后面计数解法的核心依据，也是二分答案时搜索区间的边界。可以说，整道题的三种解法都是围着这层定义转的，地基没打好，代码写出来也是蒙的。

2. 解法一：排序 + 一次遍历，最容易拿分的方案

2.1 先想清楚排序之后到底要找什么

排序法的思路非常直接。把 citations 升序排列后，假设遍历到下标 i，那么从 i 到数组末尾一共有 n - i 篇论文，这些论文的引用数都大于等于当前数字 citations[i]。如果 citations[i] 本身也大于等于 n - i，那说明至少存在 n - i 篇论文，每篇被引都不低于 n - i 次，于是 n - i 就是一个合法的 h 候选值。

因为 i 从小到大走，n - i 是从大到小变化的，所以第一次找到满足条件的 n - i，就是最大的合法 h，直接返回就行。举个例子，[3, 0, 6, 1, 5] 排序后是 [0, 1, 3, 5, 6]：

• i = 0，citations[0] = 0，n - i = 5，0 >= 5 不成立。
• i = 1，citations[1] = 1，n - i = 4，不成立。
• i = 2，citations[2] = 3，n - i = 3，3 >= 3 成立，返回 3。

这里也能看出判断条件必须用大于等于，而不是大于。如果写成大于，遇到引用数恰好等于候选值的情况就会漏判，比如 [1, 1] 这种数组。

2.2 两种排序写法：升序 return 和降序 while

升序写法刚才已经给出核心逻辑，对应 Java 代码很简洁：

class Solution { public int hIndex(int[] citations) { Arrays.sort(citations); int n = citations.length; for (int i = 0; i < n; i++) { if (citations[i] >= n - i) { return n - i; } } return 0; } }

降序写法更贴近 h 指数的原始定义，我平时考试也最常用这个：

class Solution { public int hIndex(int[] citations) { Arrays.sort(citations); int h = 0; for (int i = citations.length - 1; i >= 0; i--) { if (citations[i] <= h) { break; } h++; } return h; } }

这段逻辑是：从大往小遍历，每遇到一篇引用数比当前 h 大的论文，h 就加 1；一旦当前论文引用数小于等于 h，后面更小的论文也不可能再抬高 h，直接中断。注意判断条件是 citations[i] <= h 时 break，意味着严格大于 h 才继续计数，这样 [0] 这类边界才能得到正确结果。

2.3 复杂度分析和这个套路为什么值得背

排序的时间复杂度是 O(n log n)，遍历是 O(n)，所以整体是 O(n log n)，空间复杂度 O(1)。对于 n 最多几千的题目规模，这个方案完全是安全的，也是大多数人面试时第一个想到的解法。

“排序后找第一个满足条件的位置”这个套路不是 H 指数专属，很多数组题都有类似结构，比如求摆动序列、合并区间里的重叠判断。所以我建议把升序和降序两种写法都记住，遇到类似的排序题能直接迁移。唯一的风险点是排序函数对原始数组的影响：如果后续还想用原始顺序，记得先拷贝一份。

3. 解法二：计数数组，把复杂度压到 O(n)

3.1 核心洞察：h 永远不可能超过论文总数 n

一提到排序法，很多追求极致复杂度的人会问：能不能不排序就得到答案？可以，需要抓住一个容易被忽略的性质：论文有 n 篇，所以 h 的最大值就是 n。无论某篇论文被引了 1000 次还是 100 次，在判断“是否有 k 篇论文被引至少 k 次”时，它只能贡献 1 篇。

基于这个性质，我们可以申请一个长度为 n + 1 的计数数组 counter，其中 counter[k] 表示“被引次数恰好为 k 的论文篇数”。如果某篇论文被引次数超过 n，我们不需要为它单独开很多桶，直接把它累加到 counter[n] 里就行，因为它在所有 k 不超过 n 的判断里，效果等同于一篇“被引 n 次”的论文。

3.2 从高到低累加，累加的是什么

计数完成后，从 k = n 开始向下枚举。维护一个变量 accumulated，表示“到目前为止累加到的论文总数”，也就是“被引次数大于等于 k 的论文篇数”。每轮判断 accumulated >= k 是否成立，如果成立，k 就是答案。

为什么一定从大到小枚举？因为我们要找最大的合法 h。从 n 开始往下试，第一个满足条件的 k 自然是最大合法值。如果从 0 向上枚举，找到的是最小合法值，那就错了。

Java 实现如下：

class Solution { public int hIndex(int[] citations) { int n = citations.length; int[] counter = new int[n + 1]; for (int c : citations) { counter[Math.min(c, n)]++; } int accumulated = 0; for (int k = n; k >= 0; k--) { accumulated += counter[k]; if (accumulated >= k) { return k; } } return 0; } }

注意 k 会枚举到 0。当 k = 0 时，accumulated 已经等于全部论文数 n，一定大于等于 0，所以函数必然会在循环里 return。最后的 return 0 只是为了满足编译要求，实际上不会执行。

3.3 计数法为什么是 O(n)，以及什么时候用它

计数阶段遍历一次数组是 O(n)，累加阶段遍历 n + 1 个桶也是 O(n)，总时间复杂度 O(n)，空间复杂度 O(n)。这个解法虽然额外用了数组，但思路比排序更进阶：它把“引用次数”当成值域直接映射到下标，避开排序。

使用计数法有一个前提：值域范围可控。这里引用次数虽然可能很大，但超过 n 的部分都归并到 n，所以桶数量只有 n + 1，内存可控。如果题目的值域是一个很大的离散集合，计数法就不适合，这时还是要回到排序或哈希。这个判断过程本身就是算法功底的一部分，比背代码重要得多。

4. 解法三：二分答案，换个角度也是经典套路

4.1 为什么 h 可以二分：可行性具有单调性

看到“求最大满足某条件的值”，我第一反应永远是二分答案。H 指数的答案天生适合二分，因为它的可行性在区间 [0, n] 上是单调的：

如果 h = 5 可行，那么 h = 4 一定也可行，因为至少有 5 篇论文被引至少 5 次，那么至少有 5 篇论文被引至少 4 次。反过来，如果 h = 4 不可行，那 h = 5 更不可行，因为连 4 篇都凑不齐，不可能凑齐 5 篇。

这种“可行域是一段连续区间”的特征，正是二分答案能够成立的根本原因。我们能通过不断猜测中间值，把搜索范围缩小到答案本身。

4.2 check(mid) 函数的设计

二分的核心在于写对判断函数 check(mid)：给定候选值 mid，判断是否存在至少 mid 篇论文，每篇被引都不低于 mid。实现起来很简单，遍历一次数组，统计大于等于 mid 的论文数 count，然后返回 count >= mid。

这函数最需要抠的是大于等于。如果把条件写成大于 mid，那引用数恰好等于 mid 的论文就被排除了，答案可能偏小。这种错误在二分里尤其隐蔽，因为单看某一个 mid 可能不影响最终结果，但边界处就会差出 1。

class Solution { private boolean check(int[] citations, int mid) { int count = 0; for (int c : citations) { if (c >= mid) { count++; } } return count >= mid; } public int hIndex(int[] citations) { int low = 0, high = citations.length; while (low < high) { int mid = (low + high + 1) / 2; if (check(citations, mid)) { low = mid; } else { high = mid - 1; } } return low; } }

这里我用了“找最大可行值”的模板：mid 取上中位数，可行时收缩下界 low = mid，不可行时收缩上界 high = mid - 1。这样写能避免陷入死循环，因为 low 只有在真正可行时才向右移动，mid 不会永远等于 low。

4.3 为什么 check(mid) 为真时不能直接返回

有初学者会在 check(mid) 返回 true 时直接 return mid，这是错的。比如数组 [12, 11, 10, 5, 4, 1]，mid = 3 时确实可行，因为至少有 3 篇论文被引至少 3 次，但真正的答案是 4，因为 4 篇论文被引至少 4 次的这个事实也存在。二分算法的本质是不断逼近答案，不是找到任意一个可行解就停。

所以 check 返回 true 只能说明答案不小于 mid，要继续向上试探；返回 false 说明答案不大于 mid - 1，向左压缩。这个“答案在区间里不断收敛”的视角，比死记模板更能应对二分的变体题。

4.4 三种解法的时间空间横向对比

二分答案的时间复杂度和排序法一样，但因为每轮都要重扫数组，常数更大，实际跑起来不一定更快。我个人用它主要是为了训练“答案可行性单调性”的敏感度，这在很多难题里比这道题的本身价值更高。

5. 实战中的坑与排查经验

5.1 最容易写错的三个点

第一，判断条件混淆“大于”和“大于等于”。在降序 while 写法中，条件必须是 citations[h] > h，利用整数性质让“ > h ”等价于“ >= h + 1 ”。如果直接写成 citations[h] >= h，边界会出大问题。比如 citations = [0]，h 初始为 0，0 >= 0 成立，h 变成 1，最后返回 1，而正确答案是 0。我一开始就栽在这个地方。

第二，升序写法里把返回条件写成 citations[i] > n - i。这个错误遇到引用数恰好等于候选值时会漏判。比如 [1, 1]，排序后 i = 1 时，1 > 1 不成立，最后返回 0，正确答案是 1。所以升序一定是 >=。

第三，计数法里把超过 n 的引用次数直接丢弃，而不是归入 counter[n]。例如某篇论文被引 10000 次，它在判断 k 不超过 n 时始终应该算作有效论文，丢掉了会少计，最终答案偏小。

5.2 高错误率用例速查表

我建议把这张表存下来，写完代码后逐条对一次，基本能覆盖 90% 的边界错误。凡是答案比真实值大 1 的，优先怀疑大于等于还是大于的问题；凡是答案比真实值小 1 的，优先怀疑计数是否漏掉了某些论文。

5.3 单手验算技巧：降序列举法

不打开编辑器，你也可以快速验证答案。把数组从大到小排列，从第 1 位开始数，找到第一个满足“当前论文引用数 < 当前序号”的位置，答案就是前面的篇数。比如 [3, 0, 6, 1, 5] 降序为 [6, 5, 3, 1, 0]：

• 第 1 位 6，6 >= 1，继续；
• 第 2 位 5，5 >= 2，继续；
• 第 3 位 3，3 >= 3，继续；
• 第 4 位 1，1 < 4，停。

答案是 3。这个手算法和降序 while 代码是一一对应的，排查线上问题时特别方便。

5.4 我踩过的典型错误复盘

有一次我用升序写法提交，数组是 [0, 0, 0]，跑出答案 0，正确；换成 [0, 0, 1] 时，跑出 1，正确；再把判断改成大于等于后，我自以为稳了，结果遇到 [1, 2] 输出 2。我当时还很困惑，手动验算才发现问题：排序后 [1, 2]，i = 1 时，2 >= 1 成立，返回 1，但我代码里写的是 citations[i] > n - i，也就是 2 > 1，也能成立，怎么会错？再一查，我把数组长度当成了 n - i 的 n，应该是 n - i，而不是固定的数组长度。这个教训说明，边界错位往往不是因为判断符号，而是因为下标的基准没算对，排查时要同时看符号和下标两项。

另一次是在降序 while 写条件时用了 citations[h] >= h，遇到 [0] 返回 1，翻车。从那以后我就固定用 > h，并且每次都拿 [0] 和 [1] 两个极端用例先测一遍，这两个用例能筛掉绝大多数 off-by-one 错误。

6. 延伸：H 指数思路在真实场景中的作用

这道题虽然短小，但它把三个通用算法思想浓缩到了一起：排序后的候选值扫描、基于值域的计数优化、答案区间上的二分查找。我在实际工作中处理排行榜和阈值筛选时，也经常用到这几套思路。比如某个运营活动要求找出“至少有多少个用户的行为次数达到某个阈值”，本质上就是统计计数数组，然后从高到低累加判断，跟 H 指数的计数解法几乎一模一样。

我自己刷这道题最大的收获，不是背下了三种代码，而是养成了一种条件反射：拿到一道求最大值或最小值的题，先问自己三个问题——答案的取值范围是什么？可行性是不是单调的？值域能不能用计数桶压缩？想清楚这三个问题，选解法就顺理成章了。这套思维在后续刷更多类似题时会反复出现，比如分发糖果、分割数组的最大值、在排序数组中查找元素位置，都能看到它的影子。

最后再分享一个小技巧：刷这道题时，把三种解法都写一遍，然后用 5.2 节那张用例表逐条验证。不会花太多时间，但对理解排序、计数、二分这三种范式的区别很有帮助。你会明显感觉到，同样一道题，换一种数据组织方式，代码和复杂度就是另一番风景，这才是刷题最值得追求的部分。