H Index

274. H指数

分析

将引用次数降序排序。排序后，论文的引用次数是递减的，若第 i 篇论文（索引为 i - 1）的引用次数大于等于 i，则前面 i - 1 篇论文的引用次数也大于等于 i，，那么就有至少 i 篇论文的引用次数大于等于 i，即满足 H 指数条件

降序排序：
- 将引用次数从大到小排序，便于直接比较引用次数与当前索引 i
遍历判断：
- 从 i = n ~ 1（n 为论文总数），逐步判断
- 如果第 i 篇论文的引用次数 citations[i - 1] >= i，则满足 H 指数定义
- 返回当前 i 即为最大 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. 从大到小遍历，找到满足条件的最大 i
        for (int i = citations.size(); i > 0; -- i)
            if (citations[i - 1] >= i)
                return i;  // 找到最大 i，直接返回

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