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;
    }
};

Python 代码

1
2
3
4
5
6
7
8


class Solution:
    def hIndex(self, citations: List[int]) -> int:
      citations.sort(reverse=True)
      n = len(citations)
      for i in range(n, 0, -1):
        if citations[i - 1] >= i:
          return i
      return 0

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func hIndex(citations []int) int {
  sort.Slice(citations, func(i, j int) bool {
    return citations[i] > citations[j]
  })
  for i := len(citations); i > 0; i -- {
    if citations[i - 1] >= i {
      return i
    }
  }
  return 0
}