题目描述（中等难度）

求 指数，H 指数等于 n，代表该作者所发表的所有论文中至少有 n 篇论文的被引用次数大于等于 n。

解法一

第一次看到这个概念比较难理解，看一下 ) 的定义。

我们先按照上边提供的解法写一下代码。

我们结合下图理解一下上边的算法，把 [3,0,6,1,5] 从大到小排序，画到图中。

上边的 H-Index 是 3，在图中表现的话就是有 3 个点在直线上方（包括在直线上），其他点在直线下方。

我们从大到小排序后，其实就是依次判断点是否在直线上方（包括在直线上），如果出现了点在直线下方，那么前一个点的横坐标就是我们要找的 H-Index。

我们也可以从小到大遍历，结合下图。

我们从 0 开始遍历，依次判断点是否在直线下方，如果出现了点在直线上方（包括在直线上），那么当前点的垂线与直线交点的纵坐标就是 H-Index 了。

点的垂线与直线交点的纵坐标的求法是 n - i，n 是数组长度，i 是数组下标。

解法二

参考 这里-solution-with-detail-explanation) ，换一种思路理解。

首先如果数组的长度是 n，那么 H-Index 最大也就是 n。

我们先判断 H-Index 是不是 n，如果被引次数大于等于 n 的论文数大于等于 n，那么 H-Index 就是 n。

否则的话判断 H-Index 是不是 n - 1，如果被引次数大于等于 n - 1 的论文数大于等于 n - 1，那么 H-Index 就是 n - 1。

否则的话判断 是不是 n - 2，如果被引次数大于等于 n - 2 的论文数大于等于 n - 2，那么 H-Index 就是 n - 2。

… …

否则的话判断 H-Index 是不是 1，如果被引次数大于等于 1 的论文数大于等于 1，那么 H-Index 就是 1。

否则的话判断 H-Index 是不是 0，如果被引次数大于等于 0 的论文数大于等于 0，那么 H-Index 就是 0。

接下来的话有用到 的思想。

上边的算法中，我们每次想要知道「被引次数大于等于 N 的论文数」, N = n, n - 1, n - 2 ... 0 。

如果我们知道了被引次数等于 0 的论文数，被引次数等于 1 的论文数，被引次数等于 2 的论文数 … 被引次数等于 n - 1 的论文数，那么通过累加，被引次数大于等于 0 到被引次数大于等于 n - 1 的论文数也就知道了。

因为我们只关心被引次数大于等于 n 的论文数，所以被引次数等于 n 的论文数，所以被引次数等于 n + 1 的论文数，所以被引次数等于 n + 2 的论文数… 都不是我们关心的，我们只需要记录被引次数大于等于 的论文数。

综上，我们需要一个额外空间，分别存储被引次数等于 0 的论文数，被引次数等于 1 的论文数，被引次数等于 2 的论文数 … 被引次数等于 n - 1 的论文数以及被引次数大于等于 n 的论文数。

参考 这里-time-O(1)space-solution)，我们还能进一步的优化，我们可以利用原有的数组 citations 计数，不再开辟新的空间 buckets。

用原有数组计数的话，假设 citations[0] = 3，那么我们应该将 citations[3] = 1。但如果我们遍历到了 citations[3] 的时候，此时它代表的是被引用次数等于 3 的论文数，而不是当前论文的被引用次数。

所以我们需要区分当前数字是在计数还是表示论文的被引用次数。

有一个 trick，注意到论文被引用次数都是非负数，所以我们可以用负数计数。用 -1 代表 0， -2 代表 1， -3 代表 2… 以此类推。这样的话，从负数到它的原本含义的映射就是「先取相反数，然后再减一」。

如果当前是 -4 ，那么它代表 -(-4) - 1 = 3。

取相反数，在 中讨论过，可以通过取反加一替代，代入原来的映射 「先取相反数，然后再减一」，就是 「先取反加一，然后再减一」，所以就是 「取反」即可。

还有个问题需要解决。

假设 citations[0] = 3，那么我们应该将 citations[3] = -2，如果直接这样做的话，citations[3] 之前的数就被替代了。所以替代前，我们还需要将 citations[3] 存起来，然后重复这步。

还有一些细节，可以结合代码看，文字有些难描述。

因为我们数组大小是 n，那么只能统计 0 的 的情况，还需要一个变量单独记录被引用数大于等于 n 的论文数。

总

这道题的话，如果知道定义的话很好写。然后解法二利用原有空间的思想进行优化也经常用到。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情