[LeetCode] 274. H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining
two with no more than 3 citations each, her h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.

H 指数。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/h-index
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 二分查找

根据题目的描述我们可以知道，h 应该是有一点“单调性”的。意思是如果我们返回 h = 1，那一定对，因为肯定至少有 1 篇论文被引用的次数 >= 1。如果返回 h = 100，就不一定对了，因为不可能有 100 篇论文被引用的次数 >= 100。所以这里我们可以用二分查找，找的就是最大的 h 的值。查找的下界是 1，这个很好理解；而上界是 citations.length，这个也很好理解，因为最多也就这么多篇论文。h 的定义是跟作者发的论文数量挂钩的。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public int hIndex(int[] citations) {
        int left = 1;
        int right = citations.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (helper(citations, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    private boolean helper(int[] citations, int h) {
		// count是引用数量大于等于h的文章数量
        int count = 0;
        for (int citation : citations) {
            if (citation >= h) {
                count++;
            }
        }
        return count >= h;
    }
}

思路二 - 计数排序

建立一个 [citations.length + 1] 长度的数组 buckets，表示被引用的次数。遍历 citations，根据每篇文章的引用次数，将文章累加到每一个 bucket 里面。按照上面的例子，数组本身的长度为 5，如果遇到被引用次数大于 5 的，也一律放在下标为 5 的位置上，因为引用次数大于 5 的文章再多，都不会影响这个作者的 H 指数。解释参见这个帖子的方法二。从右往左再次遍历这个 buckets 并开始累加（注意这里累加的是文章的数量）。如果累加和大于或等于当前的 i - 也就是当前的被引用次数，我们就找到了这个 H 指数。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] bucket = new int[n + 1];
        for (int c : citations) {
            if (c >= n) {
                bucket[n]++;
            } else {
                bucket[c]++;
            }
        }
        int count = 0;
        for (int i = n; i >= 0; i--) {
            count += bucket[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }
}

JavaScript实现

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    const buckets = Array(citations.length + 1).fill(0);
    citations.forEach(citation => {
        buckets[citation >= citations.length ? citations.length : citation]++;
    });
    let count = 0;
    for (let i = citations.length; i >= 0; i--) {
        count += buckets[i];
        if (count >= i) {
            return i;
        }
    }
    return 0;
};