LeetCode 275. H 指数 II
目录
题目描述
题意分析
给一个已经升序排好的引用次数数组，求最大的
h，使得至少有h篇论文的引用次数都不少于h。返回的是这个最大的h，不是任何下标。「已经升序」这四个字是全题最重的信号。上一版题目没有这个前提，$O(n)$ 计数就是最优解；这里明确给了有序，又明确要求对数时间，等价于直接点名要在下标上做二分。
把定义翻译到有序数组上：如果选定下标
i，那么从i到末尾共有n - i篇论文，它们的引用次数都不小于citations[i]。所以「citations[i] >= n - i」成立就意味着存在一个不小于n - i的 h 指数。要让h尽量大，就要让i尽量小。数组长度可达 10^5，引用次数可以是 0，也可以远大于论文总数。全 0 数组的答案是 0；每篇引用次数都超过总篇数时答案就是
n。这两端都要能自然落进同一套边界里。数组长度也可能是 1，此时答案取决于唯一元素是否不小于 1。
解法：二分查找判定答案
核心思路
朴素做法是从左往右扫，找到第一个满足
citations[i] >= n - i的下标，答案就是n - i。这是 $O(n)$ 的，在本题的对数时间要求下不够，瓶颈在于它没有利用「数组有序」这个前提。要用二分，就必须先把「找最大的 h」改写成一个关于下标的单调可行性判断。定义谓词
P(i)为「citations[i] >= n - i」。左边citations[i]随i递增（数组升序），右边n - i随i递减，所以一旦P(i)为真，对所有更大的下标必然也为真。这就是二分成立的全部依据：P关于下标单调，数组被划分成一段连续的假区和紧随其后的一段连续的真区。于是问题变成「找到真区的第一个下标
left」，答案是n - left；若整个数组都为假，left会自然停在n，答案是n - n = 0，与「没有任何论文能贡献 h 指数」一致，不需要额外特判。循环采用闭区间
[left, right]的写法，不变量是：任何时刻，答案下标一定落在[left, right]内；left左侧的下标全部使P为假，right右侧的下标全部使P为真。循环退出时left > right，此时left恰好是第一个使P为真的位置，返回n - left即可。代码里额外加了一条
citations[mid] == h时直接返回的短路。它成立的理由是：此时mid处P为真，说明答案至少是n - mid；而想要更大的h就得往左找，可左边的citations只会更小、要求的n - i只会更大，citations[i] >= n - i中两边同时朝不利方向变化，且由于citations[mid]恰好卡在等号上，左侧任何位置都不可能再满足，所以n - mid就是最优，可以立即返回。
解题步骤
- 令
n为数组长度，二分区间取left = 0、right = n - 1。之所以在下标上二分而不是在答案值上二分，是因为有序数组的每个下标天然对应一个候选 h 值n - i，下标空间与答案空间一一对应且反向单调，省掉一次额外映射。- 循环条件写
left <= right。之所以带等号，是因为区间是闭的，left == right时还剩一个未检验的候选，漏掉它会在长度为 1 的数组或答案恰在端点时出错。- 中点用
left + (right - left) / 2计算。之所以不写(left + right) / 2，是因为在n接近 int 上界时两下标相加会溢出成负数，中点跑到区间外。- 令
h = n - mid，即「若从mid开始截取后缀，能得到的候选 h 值」。之所以每轮都重算而不是预存，是因为它完全由mid决定，是这次判定的右半边。- 若
citations[mid] == h直接返回h。之所以能短路，是因为等号意味着这个候选恰好卡满，左侧位置的引用数更小而要求更高，不可能给出更大的 h。- 若
citations[mid] < h，说明P(mid)为假，答案在右侧，令left = mid + 1。之所以是mid + 1而不是mid，是因为mid已被判定为假，留着它区间不会收缩，会死循环。- 否则
citations[mid] > h，说明P(mid)为真，mid本身可能就是答案但左边可能有更优的，令right = mid - 1。之所以敢丢掉mid，是因为left的语义保证了「若左侧全假，退出时left会正好等于mid」，答案不会丢。- 循环结束返回
n - left。之所以用left而不是right，是因为不变量规定left是第一个真位置，right停在最后一个假位置上。以
citations = [0, 1, 3, 5, 6]走一遍，n = 5。初始left = 0、right = 4。第一轮
mid = 2，h = 5 - 2 = 3，citations[2] = 3恰好等于 3，直接返回 3。人工核对：引用数为 3、5、6 的三篇论文都不少于 3 次引用，而想要 h = 4 就需要四篇不少于 4 次的，实际只有 5 和 6 两篇，不成立，所以 3 正确。再用
citations = [1, 2, 100]检验非短路路径，n = 3。初始left = 0、right = 2。第一轮mid = 1，h = 2，citations[1] = 2等于 2，返回 2。核对：2 和 100 两篇都不少于 2 次，h = 3 需要三篇不少于 3 次，第一篇只有 1 次，不成立，答案 2 正确。最后用全零数组
citations = [0, 0]检验兜底，n = 2。第一轮left = 0、right = 1、mid = 0，h = 2，citations[0] = 0 < 2，令left = 1。第二轮mid = 1，h = 1，citations[1] = 0 < 1，令left = 2，此时left > right退出，返回2 - 2 = 0，正确。
代码实现
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int h = n - mid;
if (citations[mid] == h) {
return h;
} else if (citations[mid] < h) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return n - left;
}
}
func hIndex(citations []int) int {
n := len(citations)
left, right := 0, n-1
for left <= right {
mid := left + (right-left)/2
h := n - mid
if citations[mid] == h {
return h
} else if citations[mid] < h {
left = mid + 1
} else {
right = mid - 1
}
}
return n - left
}
复杂度分析
- 时间复杂度：$O(\log n)$，凭据是每轮循环都把闭区间
[left, right]的长度至少砍掉一半（mid本身在两个分支里都被排除在新区间之外），区间长度从n降到 0 只需要对数轮，每轮内部只做常数次比较和算术。- 空间复杂度：$O(1)$，凭据是全程只用了
n、left、right、mid、h五个整数变量，没有开任何与输入规模相关的辅助结构，也没有递归栈。
关键点总结
- 输入「已排序」加上要求「对数时间」，基本等同于题面直接写着「用二分」；反过来，只要题目没给有序性，就该先怀疑二分是否根本不适用。
- 二分的前提不是数组有序，而是谓词单调。本题真正让二分成立的是
citations[i]递增与n - i递减这一对相反趋势，把它显式写出来比死记模板可靠得多。- 闭区间写法要三处协同：循环条件带等号、两个分支都把
mid排除、返回时按不变量选left或right。三者只要有一处不配套就会死循环或差一。- 让「无解」自然落在边界上（本题全假时
left = n，答案算出 0），比写一堆特判更稳，设计返回表达式时应该主动检验极端输入能否被同一个式子覆盖。- 中点一律写成
left + (right - left) / 2，这是零成本的溢出防护，没有任何理由不这么写。- 面试视角：面试官常先问无序版本怎么做（计数排序 $O(n)$），再给出有序前提追问能否更快。回答时要显式说出谓词和它的单调性证明，再写代码；如果直接默写二分而讲不出「为什么
citations[i] >= n - i是单调的」，通常会被继续追问到卡住。
易错点总结
- 循环条件写成
left < right：用例citations = [1]，区间[0, 0]一次都不进循环，直接返回1 - 0 = 1，此例侥幸正确；但citations = [0]同样返回 1，而正确答案是 0。- 判定写反成
citations[mid] > h时向右收缩：用例citations = [0, 1, 3, 5, 6]，第一轮就往错误方向走，最终返回 0 而非 3。citations[mid] < h时写left = mid：用例citations = [0, 0]，第二轮left = right = 1，mid恒为 1，区间不再收缩，程序死循环。- 返回
n - right或right + 1：用例citations = [0, 0]，退出时right = 1、left = 2，返回2 - 1 = 1，而正确答案是 0。- 直接返回
left当成答案：用例citations = [0, 1, 3, 5, 6]，即使找到第一个真位置 2，返回 2 也是错的，答案是候选 h 值n - left = 3，下标和答案不是同一个量。- 用
(left + right) / 2求中点：用例长度接近 $2^{31}$ 的数组（工程场景中的大数组），两下标相加溢出为负，mid变成负数，访问时抛越界异常。- 把
h写成n - mid - 1：用例citations = [1]，h算出 0，citations[0] = 1 > 0走右收缩分支，退出后返回1 - 0 = 1，此例仍对；但citations = [0]会因为0 == 0短路返回 0 之外的路径混乱，h的定义必须严格是「从mid到末尾的论文篇数」即n - mid。- 沿用无序版本的计数桶做法而不利用有序性：用例长度 10^5 的有序数组，虽然能得到正确答案，但时间是 $O(n)$，达不到题目明确要求的对数复杂度，面试中会被判定为没读懂题设变化。
- 先对已经有序的数组再排一次序：用例任意输入，结果正确但引入了 $O(n \log n)$ 的排序开销，比二分本身还慢，属于白白丢掉题目给的前提。
- 认为答案一定等于某个
citations[i]：用例citations = [1, 2, 100]，答案 2 恰好等于citations[1]容易造成误解；换成citations = [0, 5, 6]，答案是 2，而数组里根本没有 2，答案来自n - left的计算而不是数组元素本身。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 274. H 指数 | 中等 | 输入无序，最优解是按引用数计数后倒序累加，不能用二分 |
| 35. 搜索插入位置 | 简单 | 最基础的「找第一个不小于目标的位置」，谓词由比较直接给出 |
| 278. 第一个错误的版本 | 简单 | 谓词由接口给出而非数组，考察对「假区在前、真区在后」的抽象 |
| 162. 寻找峰值 | 中等 | 数组无序，靠相邻元素的大小关系构造局部单调性来收缩区间 |
| 1011. 在 D 天内送达包裹的能力 | 中等 | 二分对象从下标换成答案值域，需要额外写一个可行性校验函数 |