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 才是最终结果,而不是任意一个可行阈值。

自建示例

最大可行阈值位于中间:

输入:citations = [10, 8, 5, 4, 3]
输出:4
解释:有四篇论文的引用次数至少为 4;若取 h = 5,则只有三篇论文达到至少 5 次,因此最大值是 4。

所有论文都没有引用:

输入: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++ 实现

class Solution {
public:
    int hIndex(std::vector<int>& citations) {
        const int n = static_cast<int>(citations.size());
        std::vector<int> 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 指数的上界。