题目描述（中等难度）

274. H-Index - 图1

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

解法一

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

H指数的计算基于其研究者的论文数量及其论文被引用的次数。赫希认为：一个人在其所有学术文章中有N篇论文分别被引用了至少N次，他的H指数就是N。如美国耶鲁大学免疫学家理查德·弗来沃发表的900篇文章中，有107篇被引用了107次以上，他的H指数是107。

可以按照如下方法确定某人的H指数：

  1. 将其发表的所有SCI论文按被引次数从高到低排序；
  2. 从前往后查找排序后的列表，直到某篇论文的序号大于该论文被引次数。所得序号减一即为H指数。

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

  1. public int hIndex(int[] citations) {
  2.     Arrays.sort(citations); // 默认的是从小到大排序，所以后边要倒着遍历
  3.     int n = 1; // 论文序号
  4.     //倒着遍历就是从大到小遍历了
  5.     for (int i = citations.length - 1; i >= 0; i--) {
  6.         // 论文序号大于该论文的被引次数
  7.         if (n > citations[i]) {
  8.             break;
  9.         }
  10.         n++;
  11.     }
  12.     // 所得序号减一即为 H 指数。
  13.     return n - 1;
  14. }

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

274. H-Index - 图2

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

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

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

274. H-Index - 图3

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

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

这就是 这里-time-with-sort-O(n)-time-with-O(n)-space) 代码的理解了。

  1. public int hIndex(int[] citations) {
  2.     Arrays.sort(citations);
  3.     int n = citations.length;
  4.     for (int i = 0; i < n; i++) {
  5.         // 点在直线上方
  6.         if (citations[i] >= n - i) {
  7.             return n - i;
  8.         }
  9.     }
  10.     return 0;
  11. }

解法二

参考 这里-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。

否则的话判断 H-Index 是不是 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 的论文数… 都不是我们关心的，我们只需要记录被引次数大于等于 n 的论文数。

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

然后回到算法最开始，依次判断被引次数大于等于 N 的论文数是否大于等于 N 即可， N = n, n - 1, n - 2 ... 0 。

  1. public int hIndex(int[] citations) {
  2.     int n = citations.length;
  3.     int[] buckets = new int[n+1];
  4.     //计数
  5.     for(int c : citations) {
  6.         if(c >= n) {
  7.             buckets[n]++;
  8.         } else {
  9.             buckets[c]++;
  10.         }
  11.     }
  12.     int count = 0;
  13.     //依次判断被引次数大于等于 N 的论文数是否大于等于 N 
  14.     for(int i = n; i >= 0; i--) {
  15.         count += buckets[i];
  16.         if(count >= i) {
  17.             return i;
  18.         }
  19.     }
  20.     return 0;
  21. }

参考 这里-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 - 1 的情况，还需要一个变量单独记录被引用数大于等于 n 的论文数。

  1. public int hIndex(int[] citations) {
  2.     int n = citations.length;
  3.     int N = 0; // 记录引用数大于等于 n 的论文数
  4.     for (int i = 0; i < n; i++) {
  5.         int count = citations[i];
  6.         //已经记录过这个数
  7.         if (count < 0) {
  8.             continue;
  9.         }
  10.         //初始化为 0
  11.         citations[i] = -1; // -1 -> 0
  12.         //大于等于 n 的情况，用 N 统计
  13.         if (count >= n) {
  14.             N++;
  15.             continue;
  16.         }
  17.         //当前值之前是否被统计过
  18.         while (citations[count] >= 0) {
  19.             //保存当前论文被引用次数
  20.             int temp = citations[count];
  21.             //统计当前数，初始化为 1
  22.             citations[count] = -2; // -2 -> 1
  23.             count = temp;
  24.             //大于等于 n 的情况
  25.             if (count >= n) {
  26.                 N++;
  27.                 break;
  28.             }
  29.         }
  30.         //当前值之前已经被统计过，在原来的基础上减一(也就是计数加 1)
  31.         if (count < n && citations[count] < 0) {
  32.             citations[count]--;
  33.         }
  34.     }
  36.     // 全部论文引用数大于等于 n
  37.     if (N == n) {
  38.         return n;
  39.     }
  40.     int count = N;
  41.     for (int i = n - 1; i >= 0; i--) {
  42.         count = count + (~citations[i]);
  43.         if (count >= i) {
  44.             return i;
  45.         }
  46.     }
  47.     return 0;
  48. }

总

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

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

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