一 摘要

H 指数问题感觉是 leetcode 中比较冷门的一道题目，至少在过去笔试面试的经历中都没有遇到过。不过仔细看了一下，重点在于对题目的理解，同时感觉也算是相对比较简单一点的中等难度题目。本系列文章会标明引用 leetcode 解析的部分内容，重点在于整理和阐述分析过程。

二 题目描述

引用 leetcode 的描述原文如下：

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

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。

例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

提示：如果 h 有多种可能的值，h 指数 是其中最大的那个。

三 题目解析

3.1 示例

输入：citations = [3,0,6,1,5]

输出：3

解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。

  由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

3.2 分析

3.2.1 输入和输出

关于 h 的定义，题目中已经说的比较清楚。输入是一个整数数组，输出是数组对应的 h 值，这个值是唯一的。因为要的是“h 的多种可能的值中，最大的一个”。

3.2.2 计算方法分析

看到要计算的目标，是“最大”的一个，比较容易想到的是排序、贪心、动态规划等算法。而输入本身是一维整数数组，我们先尝试用对引用次数数组排序，并初始化 h 为 0，遍历引用次数数组来计算最大 h 的方法。

3.2.3 排序方法

使用的语言为 Java，java.util.Arrays 类中提供了对数组排序的方法，所以直接使用即可。代码及说明如下：

public class H1Solution {    public static int hIndex(int[] citations) {        // 数组升序排列        Arrays.sort(citations);        System.out.println(Arrays.toString(citations));        // 初始化i，记录当前遍历到的引用次数索引，从引用次数最大的开始        int i = citations.length - 1;        // 初始化h值为0        int h = 0;        while (i >= 0 && citations[i] > h) {            h++;            i--;        }        return h;    }
    public static void main(String[] args){        int[] citations = {3,0,6,1,5};        int h = hIndex(citations);        System.out.println(h);    }}

复杂度分析，数组长度为 n：

1、时间复杂度：O(nlogn)，因为上述方法中要对数组进行排序，所以最快是 O(nlogn)，“最快”的这点由 Arrays.sort()方法提供；因为后面是一次数组遍历，所以实际上复杂度为 O(nlogn+n)，简化描述为 O(nlogn)

2、空间复杂度：O(logn)，排序使用的额外空间，h 和 i 两个常量忽略不急。

3.2.4 计数排序

如果对上面的方法进行分析，就会发现算法的复杂度瓶颈在排序上。尽管 Arrays.sort()方法我们说了“最快”，但这是指基于比较的排序，所以最好的时间复杂度才是 O(nlogn)。但因为输入数组是整数数组，所以实际上是可以考虑其他方法来降低时间复杂度的。空间换时间，计数排序就是一种典型且适用于我们这个场景的方法。

引用 leetcode 解析的描述：

新建并维护一个数组 counter 来记录当前引用次数的论文有几篇，因为 h 不可能大于论文总篇数，所以对于引用次数超过论文发表数的情况，我们可以将其按照总的论文发表数来计算即可。这样我们可以限制参与排序的数的大小为 [0,n]（其中 n 为总的论文发表数），使得计数排序的时间复杂度降低到 O(n)。

从后向前遍历数组 counter，对于每个 0≤i≤n，在数组 counter 中得到大于或等于当前引用次数 ii 的总论文数。当找到一个 H 指数时跳出循环，并返回结果。

public static int hIndex(int[] citations) {        int n = citations.length, tot = 0;        int[] counter = new int[n + 1];        for (int i = 0; i < n; i++) {            if (citations[i] >= n) {                counter[n]++;            } else {                counter[citations[i]]++;            }        }        for (int i = n; i >= 0; i--) {            tot += counter[i];            if (tot >= i) {                return i;            }        }        return 0;    }