企业官网建设流程全解析

LeetCode-Go 题解：275. H-Index II 有序数组二分查找求 h 指数（Go 实现）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文基于 LeetCode-Go 仓库中 leetcode/0275.H-Index-II 的题解文档与源码，完整讲解 275. H-Index II 的题目定义、与 274. H-Index 的区别，以及如何利用「数组已升序排序」这一前提，用 O(log n) 的二分查找求出研究者的 h 指数。读完本文，你将掌握 h 指数的数学定义、二分查找边界推导方法，并能直接运行仓库内已覆盖边界用例的 Go 测试验证结果。

题目回顾：什么是 h 指数

题目给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列，要求编写方法计算出该研究者的 h 指数。

h 指数的权威定义（出自维基百科）为：一名科研人员的 h 指数是指他（她）的 N 篇论文中至多有 h 篇论文分别被引用了至少 h 次，而其余的 N − h 篇论文每篇被引用次数不多于 h 次。

官方示例

Input: citations = [0,1,3,5,6] Output: 3

数组[0,1,3,5,6]表示该研究者共有 5 篇论文，引用次数分别为 0、1、3、5、6。其中 3 篇论文（3、5、6）引用次数至少为 3，其余 2 篇（0、1）引用次数不超过 3，因此 h 指数为 3。

关键说明与进阶要求

• 取最大值：如果 h 有多种可能的值，h 指数取其中最大的那个；
• 进阶 1：本题是 274. H-Index 的延伸题，区别在于本题的citations数组保证已按升序排序；
• 进阶 2：能否将算法优化到对数时间复杂度（即 O(log n)）？

与 274 的对比：排序与否决定了算法形态

在 274. H-Index 中，输入数组无序，因此仓库内给出了两种经典做法：

1. 桶计数法（hIndex）：构建长度为n+1的桶数组，引用数超过n的论文统一计入buckets[n]，再自顶向下累加计数，找到第一个满足count >= i的下标；
2. 排序法（hIndex1）：先用快速排序把数组排好序，再从末尾向前扫描，数出连续满足citations[i] >= len(citations)-i的篇数。

而 275 题直接把「排序」这个步骤替你做完了——输入天然有序。此时若沿用线性扫描，时间复杂度仍是 O(n)；既然数组有序，就自然联想到二分查找，把复杂度降到 O(log n)。这正是本题「进阶」要求考察的核心点。

解题思路：二分查找的边界推导

核心目标是找到最大的 h，满足：至少有 h 篇论文引用次数 ≥ h。由于数组升序，数组后半段的引用次数更大，因此「引用次数 ≥ 某个阈值」的论文一定集中在数组的右半段。

仓库题解的核心判断条件是：

len(citations) - mid > citations[mid]

推导逻辑如下：

• 对于下标mid，论文数量为n = len(citations)；
• n - mid表示下标mid及其右侧的论文篇数——因为数组升序，这些论文的引用次数都不小于citations[mid]；
• 若n - mid > citations[mid]，说明即使把右侧所有论文都算上，其篇数仍然大于引用数citations[mid]，那么 h 指数的边界一定在右侧（右侧存在篇数更多且引用数更高的候选 h）；
• 反之，若n - mid <= citations[mid]，说明当前位置的篇数不足以支撑更高的 h，边界应向左收缩。

以[0,1,3,5,6]为例手动走一遍：

最终low = 2，n - low = 3，即 h 指数为 3，与官方示例一致。

Go 源码实现与逐行解析

仓库中对应实现位于 275. H-Index II.go：

package leetcode func hIndex275(citations []int) int { low, high := 0, len(citations)-1 for low <= high { mid := low + (high-low)>>1 if len(citations)-mid > citations[mid] { low = mid + 1 } else { high = mid - 1 } } return len(citations) - low }

逐行要点：

• 初始化区间：low = 0，high = n - 1，对下标区间做标准二分；
• 中点计算：mid := low + (high-low)>>1使用low + (high-low)/2的形式，避免(low+high)溢出，这是 Go 二分查找的推荐写法；
• 边界判断：len(citations)-mid > citations[mid]时说明 h 边界在右侧，low = mid + 1；否则边界在左侧，high = mid - 1；
• 返回结果：循环结束后low指向第一个满足「右侧篇数 ≤ 引用数」的位置，因此 h 指数为len(citations) - low。

函数名hIndex275采用小写首字母，符合本仓库「每个题目文件内函数以题号命名」的惯例，与 274 的实现（hIndex/hIndex1）保持一致的命名风格。

正确性与边界情况分析

二分查找正确性依赖于如下不变式：low左侧的所有位置都不可能是最终 h 边界，high右侧的所有位置也都不是。每次迭代都依据「篇数与引用数的大小关系」把不可能区间剔除一半，因此循环终止后low即为第一个满足citations[i] >= n - i的位置，n - low自然就是满足条件的最多论文篇数，即最大 h 指数。

值得注意的边界情况：

• 空数组：high = -1，循环不执行，返回0 - 0 = 0，h 指数为 0，合理；
• 单元素数组：如[1]，low = 0，mid = 0，1 > 1不成立，high = -1，返回1 - 0 = 1；
• 全零数组：如[0,0,0]，任意mid处n - mid > 0恒成立，low最终等于n，返回0。

测试用例验证

仓库为本题提供了完整的测试文件 275. H-Index II_test.go，覆盖了多组输入：

测试以表格驱动（table-driven）方式组织：question275结构体由para275（输入数组）与ans275（期望答案）组合而成，通过fmt.Printf打印每个用例的输入输出，便于对照。在仓库根目录执行以下命令即可复现：

go test ./leetcode/0275.H-Index-II/ -v -run Test_Problem275

整个仓库的测试统一通过 gotest.sh 中的go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...批量运行并生成覆盖率报告，说明该题解已纳入全仓库的自动化测试体系。

复杂度分析

• 时间复杂度：O(log n)，每次循环将搜索区间减半，无需遍历整个数组；
• 空间复杂度：O(1)，只使用了low、high、mid三个常量级变量，未申请额外存储。

对比 274 题的两种解法（桶计数 O(n) 空间、排序 O(n log n) 时间），275 题在「输入有序」的前提下用二分把时间压到对数级，这也是面试中「先问是否有序，再选算法」的典型考察点：数据的预处理状态直接决定可用算法的上界。

小结

H-Index II 是一道非常典型的「二分查找边界定位」题目：h 指数的定义把问题转化为「在有序数组中寻找分界点」，判断条件n - mid > citations[mid]巧妙地把「篇数」与「引用数」两个维度统一到下标比较上。结合 题目文档 与 源码实现，读者可以完整复现这道题的最优解，并将「有序数组 + 二分边界」的套路迁移到其他同类型问题上。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go