0274. H-Index ============= 题目信息 -------- :题号: 0274 :难度: Medium :主题: 数组、引用次数、阈值统计 :原题: `LeetCode 0274 `_ :重点: ``h`` 同时表示论文数量和最低引用阈值、返回最大可行值、输入数组未排序 题目重述 -------- 给定整数数组 ``citations``,其中 ``citations[i]`` 表示研究者第 ``i`` 篇论文获得的引用次数。返回该研究者的 H 指数:最大的整数 ``h``,使得至少有 ``h`` 篇论文各自被引用不少于 ``h`` 次,并且其余论文各自被引用不多于 ``h`` 次。 论文数量位于 ``[1, 5000]``,每篇论文的引用次数位于 ``[0, 1000]``。输入顺序没有排序保证。答案一定在 ``[0, citations.length]`` 内;只有满足条件的最大 ``h`` 才是最终结果,而不是任意一个可行阈值。 自建示例 -------- 最大可行阈值位于中间: .. code-block:: text 输入:citations = [10, 8, 5, 4, 3] 输出:4 解释:有四篇论文的引用次数至少为 4;若取 h = 5,则只有三篇论文达到至少 5 次,因此最大值是 4。 所有论文都没有引用: .. code-block:: text 输入:citations = [0, 0, 0] 输出:0 解释:不存在至少一篇引用次数不少于 1 的论文,所以只有 h = 0 满足定义。 把引用次数截断到论文数 ---------------------- 答案 ``h`` 不可能超过论文数 ``n``,因此引用次数大于 ``n`` 的论文在判断任何候选 ``h`` 时都等价于 恰好 ``n`` 次。建立 ``freq[c]`` 统计截断后引用次数为 ``c`` 的论文,再从 ``h=n`` 向下累计 ``papers``(引用次数至少为当前 ``h`` 的论文数)。第一次满足 ``papers >= h`` 的 ``h`` 就是最大可行值。 这直接对应定义中的“两部分”:累计得到的论文至少有 ``h`` 篇达到阈值;其余论文若存在, 因为不在累计集合中,引用次数小于 ``h``,自然不超过 ``h``。 正确性说明 ---------- 对每个候选 ``h``,从桶的高端累加得到的 ``papers`` 恰好是原数组中满足 ``citation >= h`` 的论文数量。故 ``papers >= h`` 当且仅当 ``h`` 可行。 从大到小首次命中返回的就是最大可行阈值;若直到 1 都不满足,``h=0`` 总是可行,返回 0。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int hIndex(std::vector& citations) { const int n = static_cast(citations.size()); std::vector frequency(n + 1, 0); for (int citation : citations) { ++frequency[std::min(citation, n)]; } int papers = 0; for (int h = n; h >= 0; --h) { papers += frequency[h]; if (papers >= h) return h; } return 0; } }; 代码分析 -------- 建立桶和反向累计都为 ``O(n)``,频次数组额外占 ``O(n)`` 空间;不需要排序,也不改变输入。 把大引用次数合并到 ``frequency[n]`` 不会影响任何 ``h<=n`` 的判断,正是利用了 H 指数的上界。