1. 先读懂H指数定义里容易踩的两个坑1.1 学术指标如何变成一道算法题H指数h-index本来是学术圈用来衡量学者产出影响力的指标由物理学家Jorge Hirsch在2005年提出。核心意思很简单一个学者有 h 篇论文每篇至少被引用 h 次那么他的H指数就是 h。注意这里取的是满足条件的最大值。LeetCode 274把这个问题原封不动搬到了算法题里给一个数组citationscitations[i]代表第 i 篇论文的引用次数让你返回H指数。这道题在LeetCode热门100题里占了一个位置面试出现的频率相当高原因是它看起来过于简单但实际做起来非常容易踩坑尤其是对定义理解不透的人很容易写出一个逻辑上自洽但答案错误的两层循环。先看题目的原始定义给定一位研究者论文被引用次数的数组被引用次数是非负整数。编写一个方法计算出研究者的 h 指数。h 指数的定义h 代表高引用次数high citations一名科研人员的 h 指数是指他至多有 h 篇论文分别被引用了至少 h 次。我第一次做这道题时脑子里第一反应是找中位数因为直觉上H指数描述的是大多数论文的引用水平。但这是错的。H指数不是平均、不是中位、不是众数它是一个累积统计量描述的是引用次数分布曲线与对角线 yx 的交点。举个例子citations [3, 0, 6, 1, 5]手动算一下引用次数 1 的论文有 4 篇3、6、1、5引用次数 2 的论文有 3 篇3、6、5引用次数 3 的论文有 3 篇3、6、5引用次数 4 的论文有 2 篇6、5答案是3。因为有3篇论文至少被引用了3次而4不满足只有2篇引用4。这就是H指数的本质引用次数的门槛抬得越高能跨过门槛的论文数就越少H指数就是让门槛高度和跨过门槛的论文数达到平衡的最大值。1.2 三个典型误区误区一试图先排序再取中间值或平均数。平均值没有任何意义[100, 0, 0, 0]平均值是25但答案是1。中位数在极端分布下也不对[5, 5, 5, 5, 5]中位数是5答案确实是5但换个例子[10, 1, 1, 1, 1]中位数是1、答案是2有2篇引用210和1不对1不2只有1篇2所以答案是1。等等我重新算[10,1,1,1,1]引用1的有5篇2的有1篇所以答案是1。这里中位数碰巧对。但如果用中位数法[6,6,6,1,1]中位数是6真实答案呢引用6的有3篇引用3的也只有3篇所以答案是3。中位数6远大于真实答案。所以用中位数/平均数去猜纯属碰运气。误区二死扣定义中其余论文引用次数不超过 h 次。说实话LeetCode的英文原版定义只说great than或equal to h的那部分没有严格要求其余论文必须小于等于h。但很多人在验证时多此一举导致把自己绕晕。实际判断条件只有一个是否有至少 h 篇论文引用次数 h。至于其他论文引用是否恰好超过h完全不影响因为h已经是至少h篇里的h如果其他论文也超过h那应该尝试更大的h。误区三用暴力两层循环但没搞清枚举方向。很多人会写成def hIndex(citations): n len(citations) for h in range(n, -1, -1): count sum(1 for c in citations if c h) if count h: return h这个逻辑是对的但时间复杂度是O(n²)。如果你在面试里第一版写出这个面试官会微笑点头然后追问能不能优化到O(n log n)甚至O(n)。这就是接下来要讲的内容——这道题考察的真正重点不是会不会遍历而是能不能利用排序或计数把对每个h都扫描一遍数组这件事省掉。2. 解法一排序法为什么是从右往左数2.1 排序后逆序扫描的数学直觉先给最直接的思路把数组降序排列[3, 0, 6, 1, 5]变成[6, 5, 3, 1, 0]然后从第一个元素开始往后数当前位置 i从0开始前面已经有 i1 个元素包括当前这些元素的值都 当前元素值。如果当前元素值 i1说明前 i1 篇论文每篇引用次数都 i1那么 h i1 是可行的。继续往后走直到某个位置元素值 位置1说明从这里开始后面的论文引用次数都不够支撑更大的h了。答案就是上一个满足条件的位置1。或者换一种更常用的写法排序后升序排列从最后一个元素往前遍历用一个计数器h记录当前找到的H指数候选值每次遇到引用次数大于 h的论文就h 1否则直接结束。为什么从右往左数因为升序排序后最右边的元素是引用次数最多的论文。我们从引用最高的论文开始数每数一篇就相当于把候选h往上抬一。核心逻辑是这里有一个很微妙的点排序后citations[i]表示当前位置的引用次数n - i表示从i到末尾一共有多少篇论文。如果citations[i] n - i说明从第i篇到最后一篇一共n-i篇论文每篇引用次数都不低于当前这篇也就都 n-i所以n-i是一个可行答案。随着i从右向左移动n-i在增大1、2、3...我们找最后最左一个满足条件的位置此时n-i最大就是最大可行h。# 解法一升序排序 逆序扫描 def hIndex(citations): citations.sort() n len(citations) h 0 for i in range(n - 1, -1, -1): # n - i 表示从 i 到末尾的论文数量 if citations[i] n - i: h n - i else: break return h2.2 另一种等价写法计数器法LeetCode官方题解里还有一种更优雅的写法本质上和上面一样但代码更短def hIndex(citations): citations.sort() h 0 for i in range(len(citations) - 1, -1, -1): if citations[i] h: h 1 else: break return h这里h从0开始每遇到一篇引用次数 h的论文就说明当前已统计的 h 篇论文之外又多了一篇引用次数至少为 h1 的论文于是 h 可以加1。因为数组是升序的从右往左扫描保证我们看的论文引用次数是递减的一旦遇到引用次数 h的就说明剩下的论文引用更低都不可能再支撑更大的h了直接break。这两种写法输出一致。第一种更好理解第二种更简洁面试时推荐先说第一种逻辑再提还可以写成第二种。我实际做题感受是第二种在边界条件下更不容易犯错因为它把 n-i的显式比较换成了 h的累计比较语义上更贴近H指数的定义。2.3 边界条件验证拿几个典型输入验证[0]排序后[0]n1从 i0 开始citations[0]0n-i10 1不成立h0。正确唯一一篇论文引用为0h0。[1]1 1h1。正确。[0,0,0]全部不满足h0。正确。[100, 100, 100]n3从右往左i2时100 1h1i1时100 2h2i0时100 3h3。返回3。注意答案不是100因为总共只有3篇论文H指数不可能超过论文总数。[1, 3, 1]排序[1,1,3]i2时3 1h1i1时1 2? 不成立break返回1。验证引用1的有3篇2的有1篇最大可行h1。正确。排序法的时间复杂度是O(n log n)空间复杂度O(1)如果允许原地排序。对于绝大多数场景这已经足够优秀了。但题目标题说两种高效解法第二种才是真正体现算法素养的解法。3. 解法二桶计数如何把时间压到O(n)3.1 核心洞察h指数的天然上界第二种解法的关键在于一个容易忽略的事实H指数的最大值不会超过论文总数 n。就算有一百篇论文每篇被引用了十万次H指数最多也只有100因为你只有100篇论文不可能得出有101篇论文引用101这种结论。这个简单的观察给了我们一个离散化的思路引用次数超过 n 的论文在计算H指数时和引用次数恰好等于 n的论文等价。因为判断 hn 时只需要知道引用 n 的论文数是否 n引用 100000 次和引用 n 次在这个判断上没有区别。所以我们可以按引用次数分桶统计桶的下标从0到n一共n1个桶。下标 i 的桶里放引用次数恰好为 i 的论文数其中引用次数大于等于 n 的论文统一放进下标 n 的桶。这一步就完成了一次遍历数组、O(n)时间把分布统计出来。3.2 桶的设计与累加过程设bucket[i]表示引用次数为 i 的论文篇数bucket[n]表示引用次数 n 的论文篇数。统计完后我们需要从高往低累加用一个变量count表示当前累计的引用次数 当前下标的论文数。从 i n 开始向下遍历count bucket[i]累加后count的含义就变成引用次数 i 的论文总数。如果count i说明 i 是一个可行H指数直接返回 i。为什么从高往低第一个满足的就是答案因为 i 从 n 递减第一个满足条件的是最大的 i而H指数要的是满足条件的最大值所以找到就返回。还是用[3, 0, 6, 1, 5]手推一遍n5初始化bucket[0..5]全0。引用3次bucket[3] 1引用0次bucket[0] 1引用6次6 n计入 bucket[5] 1引用1次bucket[1] 1引用5次bucket[5] 2原来1再加1现在 bucket [1, 1, 0, 1, 0, 2]。从 i5 开始累加i5count 0 2 22 5否i4count 2 0 22 4否i3count 2 1 33 3是返回3和真实答案一致。注意这里 i4 时没有提前返回因为虽然 count2 已经不为0但不足以支撑 h4。3.3 实现代码与细节# 解法二桶计数法O(n)时间O(n)空间 def hIndex(citations): n len(citations) bucket [0] * (n 1) for c in citations: if c n: bucket[n] 1 else: bucket[c] 1 count 0 for i in range(n, -1, -1): count bucket[i] if count i: return i return 0Java版本可以这样写class Solution { public int hIndex(int[] citations) { int n citations.length; int[] bucket new int[n 1]; for (int c : citations) { if (c n) { bucket[n]; } else { bucket[c]; } } int count 0; for (int i n; i 0; i--) { count bucket[i]; if (count i) { return i; } } return 0; } }代码里两个细节值得注意if c n而非c n。引用次数恰好等于 n 的论文和引用次数大于 n 的论文在计算H指数时的作用完全相同所以可以直接放进同一个桶。我见过有人写成c n导致bucket[n]少统计了引用次数正好为 n 的论文在小数据量时可能侥幸通过但在[n, n, n]这类用例上会出错。循环从 n 往下到 0不是从 n-1。因为 bucket[n] 里存的是引用次数 n 的论文必须参与 n 这一档的判断。如果从 n-1 开始累加等于默认忽略了引用次数超过 n 的论文答案直接少算。3.4 为什么这是高效解法桶计数法用 O(n) 的额外空间换来 O(n) 的时间复杂度。从大O角度它比排序法更优从实际运行角度在 n 很大时差距明显。比如 n10000排序法要几万次比较计数法只要两次线性扫描。核心方法论是当一个题目的答案有明确上界这里是不超过 n时可以考虑用桶/计数数组把比较问题转化为统计问题。这个套路在很多统计类题目里都好用——比如给一串 0 到 100 万的数字要统计出现频率如果最大值有上界开数组永远比排序更直接。4. 两种解法的完整对比与测试用例设计4.1 综合对比表格维度排序法桶计数法时间复杂度O(n log n)O(n)空间复杂度O(1)原数组排序O(n)桶数组是否依赖数据分布否是依赖答案上界n代码复杂度更短、更通用稍长但逻辑更直白面试观感常规思路稳加分项体现对数据范围敏感适用场景题目没给数据范围通用解法明确知道引用次数上界为 n实际刷题时两种都要掌握。排序法是保底方案桶计数法是优化方案。但注意面试官要的不是你背了两种解法而是你能讲清楚为什么桶计数可以达到O(n)。如果只会背代码不会解释答案上界 n 与桶下标的关系效果反而不好。4.2 边界测试用例清单写算法题最容易出错的永远在边界。这道题我建议至少跑这几组用例输入预期输出说明[]0空数组h0[0]0单篇论文且引用为0[1]1单篇论文引用为1[0,0,0]0全0[1,1,1]1引用次数和篇数相等[100,100,100]3引用远超nh被n限制[3,0,6,1,5]3题目示例[1,3,1]1两篇低引用拉低h[11,15]2两篇引用都超过2h2[5,5,5,5,5,5]6全部相等且等于n6篇第6行和第9行最容易错[100,100,100]答案是3不是100[11,15]答案是2不是11因为h永远不可能大于论文总数。这是新手掉得最多的坑也正好对应桶计数法里引用次数n的论文全部归入bucket[n]这个设计。4.3 实际场景中怎么选如果我在实际面试中遇到这道题会先快速确认数据规模如果citations.length在几百以内排序法完全够用没必要强行上桶计数如果 n 达到百万级排序法可能超时桶计数才是稳妥选择。LeetCode上这道题的官方数据范围是0 citations[i] 10000 citations.length 5000其实排序法已经能过但桶计数法依然值得掌握因为它对应一类更广的解法思路。另外提一句这道题在LeetCode上还有一个进阶版本 275 H指数 II输入是有序数组要求时间复杂度 O(log n)。那题就是二分查找了核心同样利用答案上界为n。学完274再去刷275会顺很多。最近周赛里也经常出现类似的统计二分组合题比如 073 爱吃香蕉的狒狒本质是通过二分查找最小可行速度和H指数的找最大可行h是对称的两种二分方向放在一起刷记忆会更深。5. 面试官视角这道题的考点与追问变体5.1 为什么它值得进热门100题这道题表面上是数学定义题实际上考察了三个程序员基本素养准确地理解非标准定义。H指数的定义不是最大/最小/平均这种常见指标它是满足某条件的所有值中最大的一个。能准确提炼出至少 h 篇论文引用次数 h这句话题目已经做对一半。意识到答案的天然上界。任何论文集合的H指数都不可能超过论文总数这个约束直接催生了桶计数法。能主动发现并利用这个上界是区分会遍历和懂算法的分水岭。复杂度优化的方向感。从O(n²)到O(n log n)到O(n)每一步优化都有明确动因减少重复扫描、利用数据分布特性。面试官听你讲这道题的思路能快速判断你是背题型还是真理解。我在模拟面试中见过不少候选人能把排序法写对但问他还能不能再优化时僵住。如果他能说出H指数最大是n所以可以用桶哪怕代码里有个别小错误我都会给正面评价——因为这种思考方式才是面试官真正要找的。5.2 常见追问与应对思路面试官可能下面的问题追问1如果论文数量是10^6引用次数上限也是10^6桶还能开吗桶数组大小是 n1也就是 10^6 1 个整数算下来大约 4MB 内存现代机器完全扛得住。但如果论文数量是 10^9桶就会爆内存此时就得退回排序法或者用哈希表做稀疏计数。追问2如果citations数组不能修改只读怎么办排序法可以改成拷贝一份再排序空间O(n)桶计数法本来就不修改原数组。此时桶计数法在空间上也和排序法打平而时间仍然占优优势更明显。追问3如果数据是流式的每来一篇论文实时返回当前H指数实时返回是个棘手的问题典型做法是维护一个大小为当前H指数的最小堆新论文引用次数大于堆顶时分两种情况处理如果堆大小不足当前h则直接入堆如果超过则替换堆顶并重新计算h。复杂度O(n log h)这是个独立的进阶题但思路可以从这道题延伸过去。追问4为什么循环里是count i而不是count i注意判别条件要严格满足至少 i 篇论文引用次数 i。当count i时恰好满足所以需要。如果写成会漏掉临界情况比如[1, 1]i1 时 count22 1依然满足返回1看起来很对但换个例子[2, 2]n2bucket[2]2i2 时 count22 2不成立继续循环到 i1 时 count2返回1而真实答案是2——直接在临界点上出错。5.3 我刷这道题的心得坦白说我第一次做这道题的时候写的是两层暴力还自以为没错。直到手动跑[3,0,6,1,5]发现自己的逻辑在为什么h3而不是2上说不通才回头仔细读定义。这题最反直觉的地方在于H指数不是找一个位置而是找一个高度。你可以把它想象成一个水库的蓄水位水位越高淹没的论文数越少H指数就是让水位和被淹没的论文数恰好持平的临界水位。排序法是沿着论文个数从大到小找水位桶计数法是沿着水位从高到低找论文数切入点不同答案一致。如果让我给一个刷题顺序建议先自己推导一遍排序法的为什么从右往左数再手推两组测试用例然后试着用桶计数法重新实现。等这两步都做完了再去刷275和073你会发现这类有上界的统计问题其实是一个家族。最后分享一个小技巧写桶计数法之前先在纸上画一条水位线。想象一个横轴是引用门槛、纵轴是论文数的直方图桶数组就是直方图的柱子从右往左移动水位线累计淹没的柱子面积第一次超过门槛高度时答案就出现了。把这个图画清楚代码基本不会写错。