H 指数

关键洞察:把引用数降序排好后,排在第 i 位(从 1 数)的论文,意味着「至少有 i 篇论文的引用 ≥ 它」。于是只要看每个位置的值够不够大就行。

起步 · 原始数组：这是原始的 5 个引用数,顺序是乱的。要用排序法,第一件事就是把它们从大到小重新排列。下面用「每一轮挑出剩下最大的、放到最左边」来演示排序。

排序 · 找位置 0 的最大：指针停在要填的位置 0。开始扫一遍找剩余最大值,先把第一个 3 当作暂定最大。

排序 · 扫到下标 2：继续往右扫,3、0 都不如它,扫到下标 2 的 6——这是目前最大的,记下它。

排序 · 扫完确认最大：剩下的 1、5 也都比 6 小,扫描结束。整段最大确实是 6,接下来把它换到位置 0。

排序 · 位置 0 = 6 ✓：6 和原来位置 0 的 3 交换,位置 0 现在是 6,锁定(变灰底)。继续填位置 1。

排序 · 选位置 1：位置 0 已锁定。在剩下的 0、3、1、5 里找最大,是 5。准备把它换到位置 1。

排序 · 位置 1 = 5 ✓：5 和位置 1 的 0 交换,位置 1 现在是 5,锁定。前两位已经是 6、5。继续位置 2。

排序 · 选位置 2：在剩下的 3、1、0 里找最大,是 3,它正好已经在位置 2,不用动。锁定位置 2。

排序 · 位置 2 = 3 ✓：位置 2 锁定为 3。剩下的 1、0 本来就是从大到小,排序完成。最终降序结果:[6,5,3,1,0]。

排序完成 · 降序就绪：排好了!现在进入第二阶段:指针从左到右走,在每个位置 i 检查 citations[i] ≥ i+1 是否成立。i+1 表示「到这一位为止,前面有多少篇论文」。

检查 · 位置 0：指针到位置 0。这是第 1 篇,问:它的引用 6 是否 ≥ 1?也就是「能不能凑出 1 篇被引 ≥1 次」。

检查 · 位置 0 ✓：6 ≥ 1,成立!说明「有 1 篇被引 ≥1 次」一定办得到,候选答案 h = 1。指针右移看能不能更大。

检查 · 位置 1：指针到位置 1。这是第 2 篇,前 2 篇里最小的就是它(5)。问:5 是否 ≥ 2?即「能不能凑出 2 篇都被引 ≥2 次」。

检查 · 位置 1 ✓：5 ≥ 2,成立!前 2 篇(6 和 5)都 ≥2 次,候选 h = 2。继续。

检查 · 位置 2：指针到位置 2。这是第 3 篇,前 3 篇里最小的是 3。问:3 是否 ≥ 3?即「能不能凑出 3 篇都被引 ≥3 次」。

检查 · 位置 2 ✓：3 ≥ 3,成立!注意恰好相等也算通过。前 3 篇(6、5、3)都 ≥3 次,候选 h = 3。

检查 · 位置 3：指针到位置 3。这是第 4 篇,值只有 1。问:1 是否 ≥ 4?即「能不能凑出 4 篇都被引 ≥4 次」。

检查 · 位置 3 ✗ 停!：1 ,失败!第 4 篇只有 1 次引用,凑不出「4 篇都 ≥4 次」。一旦失败,后面更小的更不可能,直接停。答案就是停下来前的候选 h = 3。

完成 · h 指数 = 3：结束。绿色的前 3 篇(6、5、3)就是支撑答案的论文——它们每篇引用都 ≥3,而第 4 篇撑不到 4。所以 h 指数 = 3。

为什么扫到失败就能停?因为降序后值越往右越小、要求 i+1 却越往右越大——一边降一边升,一旦交叉(失败),后面只会更不满足,所以第一个失败点就是分界线。

雷区实演 · 用 > 会怎样：假如把条件错写成 >:走到位置 2 时 3 > 3 不成立,会提前停在 h=2,少算了一篇。正确答案 3 被漏掉——这就是等号必须保留的铁证。

边界三连：记牢:h 不会超过论文总篇数。哪怕一篇被引一万次,只有 1 篇,h 也只能是 1——别被大数字带偏。

面试追问：把「O(n) 计数桶」和「升序数组可二分」讲出来,是这题进阶加分点。