274. H 指数

难度: 中等

来源: 每日一题 2023.10.29

---

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

输入：citations = [1,3,1]
输出：1

提示：

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

class Solution {
    public int hIndex(int[] citations) {

    }
}

分析与题解

---

• 贪心算法

  我们想要找到题目的题解, 我们就一定需要找到其中的规律, 核心就是有 k 篇文章最少被引用 k 次. 从中找一个最大的 k 值.

  首先, 我们先对数组进行排序. 这是从经验出发的, 因为涉及到比较大小的问题, 我们排序之后的数组更加容易找到边界.

  Arrays.sort(citations);
  

  然后, 我们需要遍历数组, 当 citations[i] 比后面的元素个数还要多, 就是我们要找到的最大的 k 值, 我们直接从 i → citations.length 的元素个数即可.

  for(int i = 0; i < citations.length; i++) {
      if (citations[i] >= citations.length - i) {
          return citations.length - i;
      }
  }
  

  如果查找一遍发现没有任何符合题意的结果, 直接返回 0.

  return 0;
  

  下面让我们一起看看整体的题解过程吧.

  class Solution {
      public int hIndex(int[] citations) {
          Arrays.sort(citations);
          int k = 0;
          for(int i = 0; i < citations.length; i++) {
              if (citations[i] >= citations.length - i) {
                  return citations.length - i;
              }
          }
          return 0;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(nlogn), 排序的时间复杂度为 nlogn
  • 空间复杂度: O(logn), HashMap和双向链表空间复杂度与所有节点的数量成线性关系.

  结果如下所示.