H 指数 II 图解题解

先说清 h 指数是什么，这题又求什么

h 指数是学者影响力的刻度：有 h 篇论文、每篇都至少被引用 h 次，这个 h 就成立，要的是能成立的最大 h。给的数组 citations 已升序（从小到大排好），citations[i] 是第 i 篇论文的被引次数。题面 citations=[0,1,3,5,6]，答案 h=3，引用 3、5、6 这 3 篇各 ≥ 3 次，凑 4 篇 ≥ 4 就不够。题目卡死 O(log n)、不许挨篇数。

从引用最多的往回数，为什么大数组会卡住

一个数法是从引用最多的往回数：数到第 k 篇就看这 k 篇是不是都 ≥ k 次，凑不齐就停。最坏从头扫到尾、比满 n 次，是 O(n)。论文上百万就走不动，而题目点名 O(log n)，把逐篇数堵死。

citations[mid] 和 n−mid 一比，分界就现出来

站在下标 mid 往右看，从它到末尾共 n−mid 篇，升序保证这批引用全都 ≥ citations[mid]。只要最矮的 citations[mid] ≥ n−mid，这 n−mid 篇就个个 ≥ n−mid 次，h 至少能到 n−mid。往右挪下标时 citations[mid] 不减、n−mid 却递减，「citations[mid] ≥ n−mid 成立吗」这个判断沿下标从不成立翻成成立、翻过去不再回头。这条单调翻转就是能二分的凭据，要找第一个成立的下标。

达标往左收、不够往右跳，答案为什么读 n − lo

用 lo、hi 圈住还没排除的下标，起手 lo=0、hi=n−1，两端算数（闭区间）。每轮取中点 mid=(lo+hi)//2 比 citations[mid] 和 n−mid：达标（≥）说明从 mid 起够格，但更靠左也许有达标起点让篇数更多，hi 退到 mid−1 往左探；不达标（<），mid 及左边都凑不齐，lo 跳到 mid+1。循环 lo ≤ hi，缩到 lo 越过 hi 停。此时 lo 停在第一个达标下标，从它到末尾有 n − lo 篇，返回 n − lo、不是 lo。

拿 [0,1,3,5,6] 逐轮列出 lo、mid、hi 和判定

n=5，lo=0、hi=4。第一轮 mid=(0+4)//2=2，citations[2]=3，n−mid=3，3 ≥ 3 达标，hi 退到 1。第二轮 mid=(0+1)//2=0，citations[0]=0，n−mid=5，0 < 5 不达标，lo 跳到 1。第三轮 lo=hi=1，mid=1，citations[1]=1，n−mid=4，1 < 4 不达标，lo 跳到 2。此时 lo=2 越过 hi=1，循环停，返回 5−2=3。

方向一记反，二分就找错那头

每轮区间砍半，最多 log n 轮，时间 O(log n)；只用 lo、hi、mid 三个指针，空间 O(1)。方向最容易记反：达标时该收 hi 往左找更靠前的起点，写成 lo=mid+1 就掉了头、起点全偏。收尾别返回 lo：它是达标起点下标，要的是到末尾的篇数 n − lo，返回 lo 等于把下标当篇数交出去。mid 也别写 (lo+hi)//2，lo+hi 会溢出，用 lo+(hi−lo)//2。

Python

class Solution:
    def hIndex(self, citations):
        n = len(citations)
        lo, hi = 0, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if citations[mid] >= n - mid:   # 右边这批够格 → 往左找更靠前的起点
                hi = mid - 1
            else:                           # 凑不齐 → 起点右移
                lo = mid + 1
        return n - lo

C++

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = (int)citations.size();
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (citations[mid] >= n - mid)   // 够格 → 往左
                hi = mid - 1;
            else
                lo = mid + 1;                // 凑不齐 → 往右
        }
        return n - lo;
    }
};

Java

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (citations[mid] >= n - mid)   // 够格 → 往左
                hi = mid - 1;
            else
                lo = mid + 1;                // 凑不齐 → 往右
        }
        return n - lo;
    }
}