11.H指数

题目

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

根据维基百科上 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

思路

翻译：数组中有h个不小于h的值，求最大的h

至少有h篇论文，每一篇至少被引用次数为h，听起来很绕，但是以用例[0, 1, 3, 5, 6]来分析：

h指数无非就是5或4或3或2或1或0
那么如果数组中最小的引用次数都大于等于5，那么其他的不用看了，h就是取最大值5
如果最小值不满足，那么如果数组中倒数第二小值如果大于等于4，那么一定有4个是大于等于4的
这就是h指数

方法一：排序

h肯定不会超过数组的长度。

[0, 1, 3, 5, 6]

从小到大排序。
排序后从头开始遍历，如果最小的值，都大于数组的size，那就是size
如果上面不满足，那第二小的值如果大于数组的size - 1，那就是size - 1
所以遍历条件就是 for (int i = 0; i < size; i ++ ) { if (nums[i] >= size - 1)}
遍历排序后的数组，如果数组中该位置的值>h，那就h++然后继续遍历下一个

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

最终的时间复杂度与排序算法的时间复杂度有关

复杂度分析:

时间复杂度：O(nlogn)，其中 n 为数组 citations 的长度。即为排序的时间复杂度。
空间复杂度：O(logn)，其中 n 为数组 citations 的长度。即为排序的空间复杂度。

方法二：计数排序

根据上述解法我们发现，最终的时间复杂度与排序算法的时间复杂度有关。

所以我们可以使用计数排序算法，新建并维护一个数组 counter 用来记录当前引用次数的论文有几篇。它的值可以是0 ~ n，所以数组的长度是n + 1

[0, 1, 3, 5, 6]

我们遍历数组 citations，将引用次数大于 n 的论文都当作引用次数为 n 的论文，然后将每篇论文的引用次数作为下标，将 cnt 中对应的元素值加 1。这样我们就统计出了每个引用次数对应的论文篇数。

counter[0] = 1
counter[1] = 1
counter[2] = 0
counter[3] = 1
// 无值，默认0
counter[4] = 0
// 引用次数为5的论文有2篇
counter[5] = 2

最后我们可以从后向前遍历数组 counter，因为要找最大的H值，所以这个时候要倒序从n到0遍历遍历，找出从后往前遍历时第一个满足引用次数>i的值，就是最大的h值。
注意要用累加，因为引用次数为5的2篇，一定也能满足引用次数>=3的条件

public class Solution {
    public 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;
    }
}

复杂度分析:

时间复杂度：O(n)，其中 n 为数组 citations 的长度。需要遍历数组 citations 一次，以及遍历长度为 n+1 的数组 counter 一次。
空间复杂度：O(n)，其中 n 为数组 citations 的长度。需要创建长度为 n+1 的数组 counter。

方法三：二分法

所谓的 h 指数是指一个具体的数值，该数值为“最大”的满足「至少发表了 x 篇论文，且每篇论文至少被引用 x 次」定义的合法数，重点是“最大”。

给定所有论文的引用次数情况为[3,0,6,1,5]，可统计满足定义的数值有哪些:

h=0，含义为「至少发表了 0 篇，且这 0 篇论文至少被引用 0 次」，空集即满足，恒成立；

h=1，含义为「至少发表了 1 篇，且这 1 篇论文至少被引用 1 次」，可以找到这样的组合，如 [3]，成立；

h=2，含义为「至少发表了 2 篇，且这 2 篇论文至少被引用 2 次」，可以找到这样的组合，如 [3, 6]，成立；

h=3，含义为「至少发表了 3 篇，且这 3 篇论文至少被引用 3 次」，可以找到这样的组合，如 [3, 6, 5]，成立；

h=4，含义为「至少发表了 4 篇，且这 4 篇论文至少被引用 4 次」，找不到这样的组合，不成立；

h=5，含义为「至少发表了 5 篇，且这 5 篇论文至少被引用 5 次」，找不到这样的组合，不成立；

实际上，当遇到第一个无法满足的数时，更大的数值就没必要找了。

基于此分析，我们发现对于任意的 citations数组（论文总数量为该数组长度 n），都必然对应了一个最大的 h 值，且小于等于该 h 值的情况均满足，大于该 h 值的均不满足。

那么，在以最大 h 值为分割点的数轴上具有「二段性」，可通过「二分」求解该分割点（答案）。

最后考虑在什么值域范围内进行二分？

一个合格的二分范围，仅需确保答案在此范围内即可。

再回看我们关于 h 的定义「至少发表了 x 篇论文，且每篇论文至少被引用 x 次」综上，我们只需要在 [0,n] 范围进行二分即可。

设查找范围的初始左边界 left 为 0，初始右边界 right 为 n。每次在查找范围内取中点 mid，同时扫描整个数组，判断是否至少有 mid 个数大于 mid。如果有，说明要寻找的 h 在搜索区间的右边，反之则在左边。

二分的本质：前半部分符合要求、后半部分不符合要求，找出符合要求的最大索引

class Solution {
    public int hIndex(int[] cs) {
        int n = cs.length;
        int l = 0, r = n;
        while (l < r) {
            // 加1 是为了防止死循环
            int mid = (l + r + 1) >> 1;
            if (check(cs, mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
    // 判断是否存在至少mid篇论文的引用次数至少为mid。
    boolean check(int[] cs, int mid) {
        int ans = 0;
        for (int i : cs) if (i >= mid) ans++;
        return ans >= mid;
    }
}

上面为什么要加1

这是因为整数除法的向下取整特性。
在计算mid时，如果使用(l+r)/2，当l和r相邻时（例如l=2, r=3），则mid=(2+3)/2=2（整数除法向下取整）。
如果此时check(mid)为真，那么我们会执行l=mid，即l=2，然后循环继续，再次计算mid=(2+3)/2=2，这样就进入了死循环。

为了避免这种死循环，我们使用(l + r + 1) / 2，使得当l和r相邻时，mid会等于r（因为(2+3+1)/2=6/2=3），然后无论走哪个分支，循环都会结束（因为执行l=3后l等于r，或执行r=mid-1=2后l等于r）。所以，加1是为了避免在只剩两个数时陷入死循环，因为我们要找的是右边界（最大值）。

例子：

citations = [3,0,6,1,5]，用上述二分法：
初始化：l=0, r=5
mid = (0+5+1)/2 = 3，检查check(3): 统计>=3的个数，为3（3,5,6）-> 满足，所以l=3
接下来：l=3, r=5，mid=(3+5+1)/2=9/2=4（整数除法取整为4），检查check(4):统计>=4的个数，有2篇（5,6）不满足4（因为需要至少4篇）
所以r=3循环结束，返回3。

class Solution {
    fun hIndex(citations: IntArray): Int {
        var left = 0
        var right = citations.size
        while (left < right) {
            val middle = (left + right + 1) / 2
            if (check(citations, middle)) {
                left = middle
            } else {
                right = middle - 1
            }
        }
        return right
    }

    fun check(citations: IntArray, target: Int): Boolean {
        var count = 0
        for (i in citations) {
            if (i >= target) {
                count ++
            }
        }
        return count >= target
    }
}

复杂度分析:

时间复杂度：O(nlogn)，其中 n 为数组 citations 的长度。需要进行 logn 次二分搜索，每次二分搜索需要遍历数组 citations 一次。
空间复杂度：O(1)，只需要常数个变量来进行二分搜索。
下一篇

邮箱：charon.chui@gmail.com
Good Luck!