当数组已经排好序，你还在从头遍历？——聊聊 H 指数 II 背后的“算法直觉”

当数组已经排好序，你还在从头遍历？——聊聊 H 指数 II 背后的“算法直觉”

作者：Echo_Wish

一、引子：H 指数 II，真的是“换个输入条件”这么简单吗？

很多人第一次看到H-Index II，心里会有一种非常强烈的既视感：

哦，这不就是 H 指数吗？
只不过数组是排好序的。

然后接下来的操作，往往是：

• 把 H 指数的解法 copy 过来
• 稍微改改
• 提交
• 过了

但如果你只是把它当成“简单版 H 指数”，
那这道题真正想考你的东西，其实已经被你错过了。

我想先给你一个结论：

H-Index II，不是考你会不会算 H 值，而是考你能不能“尊重已知信息”。

而这个“已知信息”，就是——数组已经排序。

二、问题快速回顾（不废话版）

题目给你一个数组：

citations[i]

表示第 i 篇论文的引用次数，已经按升序排列。