H Index

274. H指数

分析

将引用次数从大到小排序。排序后，论文的引用次数是递减的，若当前引用次数大于等于数量 h，则 0~h-1 也会大于 h，即满足 H 指数条件

降序排序：
- 将引用次数从大到小排序，便于直接比较引用次数与当前 h
遍历判断：
- 从 h = n ~ 1（n 为论文总数），逐步判断
- 如果第 h 篇论文的引用次数 citations[h - 1] >= h，则满足 H 指数定义
- 返回当前 h 即为最大 H 指数
未找到满足条件的 H 指数：
- 如果遍历结束都没有找到，返回 0

时间复杂度

排序需要 O(nlogn) 时间
遍历一次数组 O(n)

总体复杂度：O(nlogn)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution
{
public:
    int hIndex(vector<int>& citations)
    {
        // 1. 将引用次数降序排序
        std::sort(citations.begin(), citations.end(), std::greater<int>());

        // 2. 从大到小遍历，找到满足条件的最大 h
        for (int h = citations.size(); h > 0; --h)
            if (citations[h - 1] >= h)
                return h;  // 找到最大 h，直接返回

        // 3. 如果没有满足条件的 h，返回 0
        return 0;
    }
};