0275. H-Index II ================ 题目信息 -------- :题号: 0275 :难度: Medium :主题: 有序数组、H 指数、二分查找 :原题: `LeetCode 0275 `_ :重点: 引用次数已按非递减顺序排列、``h`` 是最大可行阈值、进阶要求对数时间 题目重述 -------- 给定整数数组 ``citations``,其中 ``citations[i]`` 表示第 ``i`` 篇论文的引用次数,并且数组已经按非递减顺序排列。返回最大的整数 ``h``,使至少有 ``h`` 篇论文各自被引用不少于 ``h`` 次,其余论文各自被引用不多于 ``h`` 次。 数组长度位于 ``[1, 10^5]``,引用次数位于 ``[0, 1000]``。答案位于 ``[0, citations.length]``,输入的有序性是本题与普通 H 指数题的重要区别。题目要求利用这一性质,把运行时间控制在 ``O(log n)``;函数不需要修改数组。 自建示例 -------- 有序数组中存在中间阈值: .. code-block:: text 输入:citations = [0, 1, 4, 5, 6] 输出:3 解释:末尾三篇论文的引用次数都不少于 3;若取 h = 4,则只有三篇论文达到至少 4 次,因此最大值为 3。 没有正的 H 指数: .. code-block:: text 输入:citations = [0] 输出:0 解释:唯一论文没有被引用,无法满足 h = 1,所以结果为 0。 把 H 指数转为有序下标条件 ------------------------- 设论文数为 ``n``,考虑排序后下标 ``i``。从 ``i`` 到末尾共有 ``n-i`` 篇论文, 而它们的引用次数都不小于 ``citations[i]``。如果: .. code-block:: text citations[i] >= n - i 那么末尾这 ``n-i`` 篇论文就证明 ``h=n-i`` 可行。随着 ``i`` 向右移动,左侧引用次数不下降, 右侧所需的论文数量下降,所以这个条件一旦成立就不会再次失败;用二分查找第一个成立的下标, 返回对应的 ``n-i``。若没有下标成立,答案为 0。 正确性说明 ---------- 第一个满足条件的 ``i`` 给出最大的 ``n-i``,且后缀中的每篇论文都至少有该数量的引用, 因此这个值可行。任何更大的 ``h`` 对应更靠左的下标;这些下标都不满足条件,说明达到该阈值的论文数不足, 所以不可能有更大的可行 H 指数。二分搜索的单调性和定义完全一致。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int hIndex(std::vector& citations) { const int n = static_cast(citations.size()); int left = 0; int right = n - 1; int answer = 0; while (left <= right) { const int middle = left + (right - left) / 2; const int possible = n - middle; if (citations[middle] >= possible) { answer = possible; right = middle - 1; } else { left = middle + 1; } } return answer; } }; 代码分析 -------- 每轮排除一半下标,时间复杂度为 ``O(log n)``,只使用固定数量的变量,额外空间为 ``O(1)``。 输入已按非递减顺序排列,代码不复制、不排序;二分查找返回的是论文数量阈值,不是某篇论文的引用次数。