H 指数的定义读起来有点绕——“至少 h 篇论文被引用了至少 h 次”。但一旦把数组排个序这条规则就变得极其直观从高到低数数到第几篇时引用次数不够了h 就是几。这个排序后逐个检查的思路虽然不是最优的但最好理解面试写这个完全够用。题目长什么样给你一个整数数组citationscitations[i]表示研究者的第i篇论文被引用的次数。计算并返回该研究者的h 指数。h 指数的定义至少发表了h篇论文且至少有h篇论文被引用次数大于等于h。如果有多种可能的值取最大的那个。输入citations [3,0,6,1,5]输出3说人话就是找一个最大的h使得有至少h篇论文的引用次数 ≥h。先理解 h 指数到底是什么h 指数本质上在衡量一个研究者的综合产出质量——不是看单篇论文引用多高而是看有多少篇论文同时达到了某个引用门槛。citations [3, 0, 6, 1, 5] → 5 篇论文 h 5? 需要 5 篇 ≥ 5 次 → 6 和 5 满足只有 2 篇不够 h 4? 需要 4 篇 ≥ 4 次 → 6 和 5 满足只有 2 篇不够 h 3? 需要 3 篇 ≥ 3 次 → 6、5、3 满足有 3 篇 ✓ 所以 h 3第一反应排序后逐个检查把引用次数从高到低排序然后从第一篇开始检查第i篇从 0 开始的引用次数是否 ≥i1。为什么是i1因为排完序后前i1篇就是引用最高的i1篇。如果第i1高的论文引用次数都 ≥i1那前i1篇的引用次数一定都 ≥i1因为排过序了前面的更大。classSolution:defhIndex(self,citations:List[int])-int:citations.sort(reverseTrue)h0fori,cinenumerate(citations):ifci1:hi1else:breakreturnh跑一遍示例 1citations [3, 0, 6, 1, 5] 排序降序: [6, 5, 3, 1, 0] i0: citations[0]6 1 ✓ → h1 (前1篇都 ≥ 1) i1: citations[1]5 2 ✓ → h2 (前2篇都 ≥ 2) i2: citations[2]3 3 ✓ → h3 (前3篇都 ≥ 3) i3: citations[3]1 4 ✗ → 停止! 后面不可能满足了 结果: h 3 ✓跑一遍示例 2citations [1, 3, 1] 排序降序: [3, 1, 1] i0: citations[0]3 1 ✓ → h1 i1: citations[1]1 2? → 1 2 ✗ → 停止! 结果: h 1 ✓为什么遇到不满足就可以直接 break因为排序是降序的。如果citations[i] i1那citations[i1]只会更小也一定 i2。所以后面都不可能满足条件了直接 break。维度值说明时间O(n log n)排序是瓶颈空间O(1)原地排序进阶计数排序O(n) 时间如果面试官追问能不能 O(n) 时间——可以。利用计数排序的思路。关键观察h 指数不可能超过论文总数n。所以引用次数大于n的对 h 指数来说等价于n——因为 h 最大就是n。classSolutionCounting:defhIndex(self,citations:List[int])-int:nlen(citations)counter[0]*(n1)forcincitations:counter[min(c,n)]1total0foriinrange(n,-1,-1):totalcounter[i]iftotali:returnireturn0跑一遍示例 1citations [3, 0, 6, 1, 5], n 5 计数引用次数 5 的归入 5: counter [1, 1, 0, 1, 0, 3] 含义: 引用0次→1篇, 1次→1篇, 3次→1篇, 5次及以上→3篇 从高到低累加: i5: total3, 3 5 → 继续 i4: total3, 3 4 → 继续 i3: total4, 4 3 → 返回 3! 结果: h 3 ✓total的含义是引用次数 ≥ i 的论文总数。从n往下找第一个满足total i的i就是 h 指数。维度值说明时间O(n)计数 O(n) 遍历 O(n)空间O(n)counter 数组两种解法放在一起看解法时间空间思路排序法O(n log n)O(1)排序后逐个检查最直观计数排序O(n)O(n)引用次数计数从高到低累加面试时先写排序法然后主动说如果要求 O(n)可以用计数排序——这种递进思考是加分项。这道题教会我什么h 指数的本质是一个门槛问题h 指数在找一个平衡点论文数量和引用次数取较小值时的最大值。排序后这个平衡点变成了第 i 篇论文的引用次数是否还能撑住 i1 这个门槛——非常直观。排序是简化问题的利器原始数组是无序的很难直接判断有几篇论文引用次数 ≥ h。但排序后问题变成了从前往后数数到第几个时引用次数不够了——从 O(n²) 的枚举退化成 O(n) 的扫描。排序虽然花了 O(n log n)但把问题的复杂度降了一个量级。大于 n 的引用次数等价于 n这个技巧计数排序中min(c, n)这个操作很巧妙——h 指数最大就是 n总共只有 n 篇论文所以引用 100 次和引用 n 次对 h 指数来说没有区别。这个截断思想在处理值域很大但有效范围有限的问题时非常有用。完整测试代码fromtypingimportListclassSolution:defhIndex(self,citations:List[int])-int:citations.sort(reverseTrue)h0fori,cinenumerate(citations):ifci1:hi1else:breakreturnhif__name____main__:sSolution()citations[3,0,6,1,5]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[1,3,1]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[100]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[0]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[1,1,1]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[4,4,0,0]print(f输入:{citations}, 输出:{s.hIndex(citations)})相关题目推荐LeetCode 275 · H 指数 II引用次数已排序用二分查找优化到 O(log n)LeetCode 215 · 数组中的第K个最大元素同样是排序/计数的思路
LeetCode 274 · H 指数：排序后一条规则搞定
发布时间：2026/6/5 20:58:11
H 指数的定义读起来有点绕——“至少 h 篇论文被引用了至少 h 次”。但一旦把数组排个序这条规则就变得极其直观从高到低数数到第几篇时引用次数不够了h 就是几。这个排序后逐个检查的思路虽然不是最优的但最好理解面试写这个完全够用。题目长什么样给你一个整数数组citationscitations[i]表示研究者的第i篇论文被引用的次数。计算并返回该研究者的h 指数。h 指数的定义至少发表了h篇论文且至少有h篇论文被引用次数大于等于h。如果有多种可能的值取最大的那个。输入citations [3,0,6,1,5]输出3说人话就是找一个最大的h使得有至少h篇论文的引用次数 ≥h。先理解 h 指数到底是什么h 指数本质上在衡量一个研究者的综合产出质量——不是看单篇论文引用多高而是看有多少篇论文同时达到了某个引用门槛。citations [3, 0, 6, 1, 5] → 5 篇论文 h 5? 需要 5 篇 ≥ 5 次 → 6 和 5 满足只有 2 篇不够 h 4? 需要 4 篇 ≥ 4 次 → 6 和 5 满足只有 2 篇不够 h 3? 需要 3 篇 ≥ 3 次 → 6、5、3 满足有 3 篇 ✓ 所以 h 3第一反应排序后逐个检查把引用次数从高到低排序然后从第一篇开始检查第i篇从 0 开始的引用次数是否 ≥i1。为什么是i1因为排完序后前i1篇就是引用最高的i1篇。如果第i1高的论文引用次数都 ≥i1那前i1篇的引用次数一定都 ≥i1因为排过序了前面的更大。classSolution:defhIndex(self,citations:List[int])-int:citations.sort(reverseTrue)h0fori,cinenumerate(citations):ifci1:hi1else:breakreturnh跑一遍示例 1citations [3, 0, 6, 1, 5] 排序降序: [6, 5, 3, 1, 0] i0: citations[0]6 1 ✓ → h1 (前1篇都 ≥ 1) i1: citations[1]5 2 ✓ → h2 (前2篇都 ≥ 2) i2: citations[2]3 3 ✓ → h3 (前3篇都 ≥ 3) i3: citations[3]1 4 ✗ → 停止! 后面不可能满足了 结果: h 3 ✓跑一遍示例 2citations [1, 3, 1] 排序降序: [3, 1, 1] i0: citations[0]3 1 ✓ → h1 i1: citations[1]1 2? → 1 2 ✗ → 停止! 结果: h 1 ✓为什么遇到不满足就可以直接 break因为排序是降序的。如果citations[i] i1那citations[i1]只会更小也一定 i2。所以后面都不可能满足条件了直接 break。维度值说明时间O(n log n)排序是瓶颈空间O(1)原地排序进阶计数排序O(n) 时间如果面试官追问能不能 O(n) 时间——可以。利用计数排序的思路。关键观察h 指数不可能超过论文总数n。所以引用次数大于n的对 h 指数来说等价于n——因为 h 最大就是n。classSolutionCounting:defhIndex(self,citations:List[int])-int:nlen(citations)counter[0]*(n1)forcincitations:counter[min(c,n)]1total0foriinrange(n,-1,-1):totalcounter[i]iftotali:returnireturn0跑一遍示例 1citations [3, 0, 6, 1, 5], n 5 计数引用次数 5 的归入 5: counter [1, 1, 0, 1, 0, 3] 含义: 引用0次→1篇, 1次→1篇, 3次→1篇, 5次及以上→3篇 从高到低累加: i5: total3, 3 5 → 继续 i4: total3, 3 4 → 继续 i3: total4, 4 3 → 返回 3! 结果: h 3 ✓total的含义是引用次数 ≥ i 的论文总数。从n往下找第一个满足total i的i就是 h 指数。维度值说明时间O(n)计数 O(n) 遍历 O(n)空间O(n)counter 数组两种解法放在一起看解法时间空间思路排序法O(n log n)O(1)排序后逐个检查最直观计数排序O(n)O(n)引用次数计数从高到低累加面试时先写排序法然后主动说如果要求 O(n)可以用计数排序——这种递进思考是加分项。这道题教会我什么h 指数的本质是一个门槛问题h 指数在找一个平衡点论文数量和引用次数取较小值时的最大值。排序后这个平衡点变成了第 i 篇论文的引用次数是否还能撑住 i1 这个门槛——非常直观。排序是简化问题的利器原始数组是无序的很难直接判断有几篇论文引用次数 ≥ h。但排序后问题变成了从前往后数数到第几个时引用次数不够了——从 O(n²) 的枚举退化成 O(n) 的扫描。排序虽然花了 O(n log n)但把问题的复杂度降了一个量级。大于 n 的引用次数等价于 n这个技巧计数排序中min(c, n)这个操作很巧妙——h 指数最大就是 n总共只有 n 篇论文所以引用 100 次和引用 n 次对 h 指数来说没有区别。这个截断思想在处理值域很大但有效范围有限的问题时非常有用。完整测试代码fromtypingimportListclassSolution:defhIndex(self,citations:List[int])-int:citations.sort(reverseTrue)h0fori,cinenumerate(citations):ifci1:hi1else:breakreturnhif__name____main__:sSolution()citations[3,0,6,1,5]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[1,3,1]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[100]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[0]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[1,1,1]print(f输入:{citations}, 输出:{s.hIndex(citations)})citations[4,4,0,0]print(f输入:{citations}, 输出:{s.hIndex(citations)})相关题目推荐LeetCode 275 · H 指数 II引用次数已排序用二分查找优化到 O(log n)LeetCode 215 · 数组中的第K个最大元素同样是排序/计数的思路
