【面试经典150题】H 指数

题目链接

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

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

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

---

关键就是这句“至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次”，简单点说就是找出 h 个元素，里面每个值都大于等于 h。

方法1：

那么我们可以从 0 开始枚举，每枚举一个数就遍历一次数组检查其合法性，这样时间复杂度就为 $O(Max(citations)\ast citations.length)$，最多执行 5*10^6 次。

/**
 * @param {number[]} citations
 * @return {number}
 */

var hIndex = function (citations) {
    let k = 0;
    let candidate=0;
    while (k <= citations.length) {
        let count = 0;
        for (let i = 0; i < citations.length; i++) {
            citations[i] >= k && count++;
            if (count >= k && k !== 0) {
                candidate = k;
                break;
            }
        }
        k++;
    }
    return candidate;
};

在 leetcode 上的运行时间击败率太低。

我们另寻他路。

方法2：

将数组进行从大到小的排序，往后遍历，自增量 i 加上 1 就是当前发表论文的最大数量，而当前值 citations[i] 就是其中的最小值，只要满足 citations[i]>=i+1就是我们要寻找的最大的 H 指数。

/**
 * @param {number[]} citations
 * @return {number}
 */

var hIndex = function (citations) {
    citations.sort((a, b) => b - a);
    let h = 0;
    for (let i = 0; i < citations.length; i++){
        if (citations[i] >= i + 1) {
            h = i+1;
        } else {
            return h;
        }
    }
    return h;
};

sort 排序的算法是该方法的时间复杂度的主要开销，其底层实现做了很多优化。

V8引擎中数组的sort源码

源码注释说：This file implements a stable, adapative merge sort variant called TimSort.

意思是说它是一个稳定的自适应归并排序，称为 TimSort。