企业官网建设流程全解析

LeetCode 274这道题，我印象很深。不是因为它难，恰恰相反，它看起来简单得过分，但我在面试候选人时拿它当热身题，十个人里有六个会在边界条件上翻车，剩下四个里还有两个会把H指数的定义理解偏了。这道题在LeetCode上的编号是274，题目名叫H-Index，中文一般叫H指数。它的应用场景非常具体——评价一个科研工作者的论文产出影响力，但在算法面试里，它考察的是你对"定义转换成代码"这件事的理解深度。

这篇文章不打算只贴一份能通过的代码。我会把这道题背后的知识点拆开揉碎，讲清楚为什么H指数的定义里藏着对称条件，为什么计数做法是这道题的最优解，以及哪些边界输入是真正区分"背过题"和"真会了"的分水岭。无论你是准备校招、社招，还是在刷LeetCode Hot 100的过程中路过274，这篇都值得花十分钟看完——尤其是那些已经能AC但总觉得哪里没想透的人。

1. 一道容易想简单但真上考场会翻车的题

先还原一下题目本身。给定一个数组citations，citations[i]表示第i篇论文被引用的次数。要求计算这个研究者的 H 指数。H 指数的定义是：一个人至多有 h 篇论文分别被引用了至少 h 次。换句话说，找最大的 h，使得数组里有至少 h 个数不小于 h。

第一次看到这个定义，绝大多数人的第一反应是"这不明摆着排序题吗"。确实，排序是最直觉的路径。把引用次数从大到小排个序，然后从前往后数，只要当前论文的引用次数大于等于它前面的篇数，就继续往下数。这个思路没错，但实现起来有个特别容易踩的坑：到底是用citations[i] >= i + 1还是citations[i] > i？判断条件差一个等号，结果就完全不一样。

我见过有人把代码写成这样：

def hIndex(self, citations): citations.sort(reverse=True) h = 0 for c in citations: if c > h: h += 1 return h

这段代码在 LeetCode 上能通过，但它其实是取巧——利用了一个反直觉的性质：排序后，从前向后遍历，h增到不能再增时，h就是答案。c > h这个条件能成立，说明当前这篇论文的引用次数至少能支撑"再多一篇达到 h+1 次引用"这一要求。这个写法很优雅，但它没有直接从定义出发，导致很多人写完代码后，被面试官追问一句"为什么c > h而不是c >= h"就卡住了。

面试官问这个问题不是刁难你，他是想确认你是真的理解了 H 指数的本质，还是背了个模板。c > h和c >= h的区别，本质上是"新增这篇论文后，能否把 h 值再往上抬一格"的问题。如果c == h，说明这篇论文的引用次数刚好等于当前的 h 值。此时如果把 h 增加到 h+1，那么这篇论文的引用次数 c 就不满足"至少 h+1 次"了，所以 h 不能增加。这个逻辑埋在代码里只有一行，但背后是对定义里"至少"两个字的精确把控。

另外还有一个很多人忽略的前提：H 指数一定有上界。一个人论文总数是 n，那么 H 指数最大也不可能超过 n。这一点看似废话，但它是计数解法的基础，也是后面推二分边界的关键。把这句话刻在脑子里，这道题就成功了一半。

2. H指数的定义里藏着"对称条件"：先做减法再找答案

H 指数的完整定义其实有两句话：一个科学家的 h 指数为 h，当且仅当其发表的论文中至少有 h 篇被引用了至少 h 次，且其余论文的被引次数不超过 h 次。很多人只看前半句，把后半句"其余论文不超过 h 次"直接忽略了。前半句保证下限，后半句保证上限，两者合在一起才构成"恰好为 h"的完整条件。

这也是为什么我在刷题时坚持从定义本身出发，而不是直接套排序模板。举个例子，假设一个研究者有 5 篇论文，引用次数分别是[3, 0, 6, 1, 5]。排序后得到[0, 1, 3, 5, 6]。现在要找最大的 h。从 h = 5 开始尝试（因为 n = 5），检查是否有至少 5 篇论文引用次数 ≥ 5？只有 6 和 5 两篇，不满足，h 减一。检查 h = 4，至少 4 篇论文引用 ≥ 4？只有 6 和 5，还是不满足。检查 h = 3，至少 3 篇论文引用 ≥ 3？6、5、3 三篇，满足。再看后半句，剩余两篇引用次数 1 和 0 都不超过 3，也满足。所以答案是 3。

注意一个细节：验证 h = 3 时，我从排序后的数组里找到了 3 篇满足条件的论文，但这 3 篇正好是数组的后三个位置。这个"正好"不是巧合。排序后数组是递增的，如果第n - h个元素（0-based 索引）的值 ≥ h，就说明从那个位置往后的 h 篇论文都满足引用次数 ≥ h。如果第n - h个元素的值 < h，说明能凑够 h 篇"引用次数 ≥ h"的论文都凑不出来，更不用说剩余论文的上限条件了。后半句要求的"其余论文 ≤ h 次"在递增数组中天然满足，因为第n - h个元素本身就是剩余部分的最大值，它只要满足"≥ h"这个条件就自动意味着它前边的元素都 < h（如果存在相等的情况，说明 h 还能继续往上试探，当前 h 不是最大）。

所以这道题的排序解法可以浓缩成一行核心判断：citations[n - i] >= i，其中i从 1 到 n 遍历，表示当前假设的 h 值。这个判断我第一次看到的时候觉得有点像魔法，后来想明白了，它本质上是把"至少有 h 篇论文满足条件"这个存在性判断转化成了"排序后第 n-h 个元素的值 ≥ h"这个位置判断。排序的价值就在这里——把无序的"至少 h 篇"变成了有序的"从某个位置往后数 h 篇"。

3. 三条解题路径，对应三类常考知识点

3.1 排序做法：O(n log n)的高性价比方案

最直接的实现是先从大到小排序，然后顺序遍历。注意这里有一个我上面提到的易错点：遍历时比较的是引用次数和已累计的篇数，而不是和数组索引的比较。很多人写citations[i] > i，这在某些用例下恰好能过，但在[1, 1, 1, 1, 1]这种全部相等的例子上就会出错。

正确的排序做法有两种写法。第一种是降序遍历：

def hIndex(self, citations): citations.sort(reverse=True) h = 0 while h < len(citations) and citations[h] > h: h += 1 return h

核心逻辑是citations[h] > h：当第 h 篇论文（0-based）的引用次数严格大于 h 时，说明目前有h+1篇论文的引用次数至少是h+1，所以 h 可以继续增长。一旦遇到citations[h] <= h，H 指数就停在当前值。这里有个理解上的别扭之处：citations[h]是在 0-based 索引下取值，但它对应的语义是"第 h+1 篇论文"，而h本身代表的是"当前累计的满足条件的论文数"，所以判断条件是严格大于而不是大于等于。

第二种是从小到大排序后从后往前遍历：

def hIndex(self, citations): citations.sort() n = len(citations) for i in range(n): if citations[i] >= n - i: return n - i return 0

这两种写法时间复杂度都是 O(n log n)，空间复杂度 O(1)（原地排序）。在真实面试里，我建议你两种都掌握，因为面试官很可能让你对比两种写法的差异，考察的正是你对索引和语义之间映射关系的敏感度。

3.2 计数做法：O(n)时间换空间的"鸽巢"思路

排序解法已经足够优雅，但 LeetCode 274 的最佳解法其实是计数排序思想。为什么能做到 O(n)？因为 H 指数的最大可能值不会超过 n（论文总数），所以引用次数超过 n 的论文，其实和引用次数等于 n 的论文在 H 指数的计算里没有区别——都顶格算。这就是一个天然的"鸽巢"：我们只需要一个长度为 n+1 的桶，把引用次数映射进去，超过 n 的全部塞进最后一个桶。

def hIndex(self, citations): n = len(citations) buckets = [0] * (n + 1) for c in citations: if c >= n: buckets[n] += 1 else: buckets[c] += 1 count = 0 for i in range(n, -1, -1): count += buckets[i] if count >= i: return i return 0

这段代码的巧妙之处在最后那个反向遍历。从最大的引用次数 n 开始，逐个往下累加论文数量count。当count >= i时，说明引用次数至少为 i 的论文数已经不少于 i 篇，此时 i 就是答案。为什么不是count > i？仔细想想，如果count == i，那么恰好有 i 篇论文引用次数 ≥ i，这不正是 H 指数为 i 的定义吗？所以必须用>=。

这个计数方法的技术内核是"引用次数大于 n 的论文对答案没有额外贡献"，这句话让桶的上界收敛到了 O(n)。在实际刷题中，这个思想还会延伸到其他场景，比如"求数组中出现次数超过一半的元素"也可以用类似的空间换时间思路，但 274 的计数解法更纯粹，因为它用到了题目本身的数学性质。

3.3 二分做法：把 h 当成答案空间来猜

第三种思路是二分答案。既然 H 指数的取值范围是[0, n]，而且 H 指数具有单调性——如果 h 满足条件，那么所有比 h 小的值一定也满足条件（直观想，要求越低越容易满足）——那就可以在答案空间里二分查找最大的可行 h。

def hIndex(self, citations): n = len(citations) lo, hi = 0, n while lo < hi: mid = (lo + hi + 1) // 2 count = sum(1 for c in citations if c >= mid) if count >= mid: lo = mid else: hi = mid - 1 return lo

这里有两个细节值得注意。第一，mid的取值用了(lo + hi + 1) // 2而不是(lo + hi) // 2，这是为了向上取整，避免死循环。这种"找右边界"的二分模板和"找左边界"的模板不同，写错会导致无限循环，这是二分题里很经典的坑。第二，每次 check 都需要遍历一次数组，所以整体时间复杂度是 O(n log n)，空间 O(1)。乍一看二分解法并没有比排序解法更优，但它的价值在于代码模板的复用性，以及对"答案空间单调性"这一底层思维的训练。

三种解法横向对比一下：

顺带说一句，二分做法里不少人会尝试"在排序后的数组里二分"来把 check 的复杂度降到 O(log n)，这样整体就变成 O(n log n) 但每次 check 更快。我试过，代码会更长，实际收益有限，刷题阶段不推荐过度优化。

4. 最容易错的四类边界输入，以及真实提交里我踩过的坑

这道题在 LeetCode 上的通过率不算高，核心原因就是边界条件刁钻。我把自己在提交和平时给人 review 代码时踩过的坑整理一下，按杀伤力排序。

第一类：空数组。citations = []时，没有论文，H 指数当然是 0。排序解法里while h < len(citations)直接不进入循环，返回 0，没问题。但如果你写的是计数法，buckets = [0] * (0 + 1)也能跑通。真正的坑在于有些人会试图直接访问citations[0]来判断，这在空数组下直接 IndexError。千万别把边界判断写死。

第二类：全部引用为 0。比如citations = [0, 0, 0]，答案是 0。排序后是[0, 0, 0]，降序版本的citations[h] > h在 h = 0 时就判断0 > 0为假，直接返回 0。这个用例看着简单，但很多人会写成>=导致返回 1。前面说过，>和>=的区别恰恰在这里体现。

第三类：单篇论文。比如citations = [1]，答案是 1（1 篇论文被引用至少 1 次）。如果写成排序后citations[h] > h，h = 0 时1 > 0成立，h 变为 1，下一轮citations[1]越界，但 while 条件h < len(citations)挡住了越界，返回 1。如果是二分写法，lo = 0, hi = 1, mid = 1，checkcount >= 1成立，lo = 1，返回 1。都正确。但如果把计数法的count >= i写成count > i，这里就会错误返回 0。这个坑我见过太多次了。

第四类：密集重复值。citations = [1, 1, 1, 1, 1]，答案是 1。排序法降序版：h = 0 时1 > 0成立，h = 1；接着1 > 1不成立，返回 1。计数法：buckets[1] = 5，反向遍历：i = 5 时 count = 0，不满足；i = 4 时 count = 0；直到 i = 1 时 count = 5，5 >= 1，返回 1。这一步揭示了计数法的关键：反向遍历时，count 是"引用次数至少为 i 的论文总数"，它是常量，只有 i 在变。count >= i成立时，i 是否尽可能大？从大到小遍历保证了第一个满足条件的 i 一定最大。

还有一个我在真实刷题中被坑过的输入，citations = [100]。这里引用次数 100 远超论文总数 1，答案却是 1。排序法：1 > 0成立，返回 1。计数法：100 >= n，塞进buckets[1]，反向遍历 i = 1 时 count = 1，1 >= 1，返回 1。这个用例本身不难，但它验证了"超过 n 的引用次数要按 n 处理"这个预设，很多人写计数法时忘了这一步，导致桶数组长度不够或者索引越界。

你可能会觉得这些都是小概率输入，但算法题被扣分往往不是因为主路径没写对，而是边界用例没守住。面试官特别喜欢在这些输入里挑一个来考你，因为这些值能一眼看出你是"背了模板"还是"真正懂了定义"。

5. 从274延伸出去：这几个知识点才是这道题的隐藏考点

5.1 计数思想与"引用次数上界"的变式应用

274 的计数解法中，桶数组长度是n + 1而不是max(citations) + 1，这个"压上界"的处理是很多类似题目的通用策略。凡是碰到 "有 n 个数据，值域可能远大于 n，但只关心相对大小或阈值" 的问题，都可以考虑用桶来压缩值域。典型例子是 LeetCode 215 数组中的第 K 个最大元素，如果值域较小可以用桶排序做到 O(n)；还有 LeetCode 451 根据字符出现频率排序，也是先统计频次再按桶输出。

另外，"超过上界的值按上界处理"这个技巧在分布式系统里也有对应场景——比如统计超大日志文件中 IP 出现次数时，不会为每个 IP 建一个计数器，而是用定长数组加哈希映射来压缩。刷 274 时能意识到这一点，就比单纯过题多一层收获。

5.2 从274到275：排序输入与复杂度升级的经典套路

LeetCode 275 是 H-Index II，题目几乎一样，但明确告诉你citations是升序排列的，要求时间复杂度为 O(log n)。这就是逼你用二分，而不是排序。274 和 275 放在一起刷，正好能体会"输入的有序性如何改变算法选择"。

275 的二分写法有一个隐蔽的地方：数组是升序，H 指数对应的是"从某个位置到结尾的元素数量"和"该位置元素值"的关系。判断条件可以写成citations[mid] >= n - mid，成立时说明后半段有n - mid篇论文满足条件，可以把左边界右移；否则右边界左移。这个模板和本文 3.3 节给的二分答案模板不同，前者是"在数组中二分位置"，后者是"在答案空间中二分数值"。两种二分应对不同的问题，但都考察同一件事——单调性判断。

如果你刷题时经常把 274 和 275 的解法搞混，我的建议是强制自己在笔记里分别写清楚：274 优先用计数法（因为不要求 O(log n)），275 必须用二分（因为输入有序）。把两题的输入约束和最优解法对照着记忆，比单独刷十遍记得牢。

5.3 这个知识点在面试评价体系里的定位

从面试角度说，274 通常被归为"考察代码基本功和边界意识"的中等题。它不像动态规划那样需要复杂的转移方程，也不像图论那样需要背模板，它考的是你能否把一个数学定义精确地翻译成循环条件和边界判断。这种能力恰恰是很多候选人最薄弱的环节——不是不会写代码，而是在"定义到代码"的翻译过程中出现了语义偏差。

我在面试中见过一个很有意思的现象：候选人写排序解法，AC 之后我问"为什么这题的答案不可能超过论文总数"，有人能立刻说出"因为 H 指数要同时满足剩余论文不超过 h 次，h 再大就没有足够多的论文来支撑了"，有人会愣一下然后说"好像是这样"。这两类候选人写出的代码可能完全一样，但对知识点的吸收程度完全不同。前者即使今天没见过这道题，遇到新题也能迁移思考；后者只是暂时记住了答案。我写这篇文章的目的，就是希望你是前者。