#H 指数

#题目描述

想象你是一位作家，桌上摆着你写过的所有书。每一本书下面都贴着一个标签，写着有多少读者读过它。

H 指数其实是在玩一个“名副其实”的游戏：

如果你宣称自己的水平是 3，那么你必须同时满足两个硬条件：你手里至少要有 3 本书。这 3 本书里，每一本都得有至少 3 个人读过。

如果你想把水平提到 4，对不起，你不仅得有 4 本书，而且这 4 本书每一本的读者都得达到 4 个或更多。

这里的难点在于“制衡”：如果你只有 1 本惊世之作，被引用了 1 万次，但其他书没人看，你的 h 指数也只有 1。因为你拿不出第 2 本被引用 2 次的书。

如果你写了 100 本书，但每本都只有 1 个人看，你的 h 指数也只有 1。因为你拿不出 2 本被引用 2 次的书。

它衡量的是一种“稳健的产出”——你既要写得多，还要保证写出来的每一本都有一定的分量。

#思路分析

计算 h 指数有两种常见思路。

第一种是排序法：我们先将所有论文的引用次数从高到低排序，然后依次判断有多少篇论文的引用数大于当前编号，直到不满足条件为止。

排序法直观易懂，但时间复杂度为 O(n log n)。

第二种是计数桶法：我们统计每个引用次数出现的论文数量，并将引用次数大于等于论文总数的都归入最后一个桶。随后从高到低累加每个桶中的论文数，直到累计的论文数不少于当前引用数为止，此时的引用数就是最大的 h 指数。计数桶法避免了排序，能在线性时间内完成计算，适合大数据量场景。

#示例代码

/**
 * 计算学者的 h 指数（排序法）。
 *
 * @param citations - 每篇论文的引用次数数组
 * @returns h 指数
 */
export function hIndexBySort(citations: number[]): number {
  // 复制一份数组，避免修改原始数据
  const nums = [...citations].sort((a, b) => b - a); // 降序排列
  const len = nums.length;
  let h = 0; // h 指数初始为 0

  // 遍历排序后的数组
  // h 代表当前尝试的 h 指数
  // nums[h] > h 表示有超过 h 篇论文引用数大于 h
  while (h < len && nums[h] > h) {
    h++;
  }
  // 返回最终的 h 指数
  return h;
}

/**
 * 通过计数桶法计算 h 指数。
 *
 * @param citations - 每篇论文的引用次数数组
 * @returns h 指数
 */
export function hIndexByBuckets(citations: number[]): number {
  const n = citations.length;
  // 创建 n+1 个桶，buckets[i] 表示引用数为 i 的论文数，buckets[n] 表示引用数 >= n 的论文数
  const buckets = new Array(n + 1).fill(0);

  // 统计每个引用数出现的次数
  for (const c of citations) {
    if (c >= n) {
      // 引用数大于等于 n 的论文都归到最后一个桶
      buckets[n]++;
    } else {
      // 其余归到对应桶
      buckets[c]++;
    }
  }

  let count = 0; // 记录累计论文数
  // 从后往前遍历桶，寻找最大的 h 使得有至少 h 篇论文引用数 >= h
  for (let i = n; i >= 0; i--) {
    count += buckets[i];
    if (count >= i) {
      // 找到第一个满足条件的 i，即为 h 指数
      return i;
    }
  }
  // 理论上不会走到这里，返回 0 兜底
  return 0;
}

#复杂度分析

• 时间复杂度：O(n)，其中 n 为论文数量。
• 空间复杂度：O(n)，需要一个长度为 n+1 的桶数组。

#示例演示

以 citations = [3, 0, 6, 1, 5] 为例，核心步骤如下：

从后往前累加，累计到 buckets[3] 时，累计论文数为 3，满足有 3 篇论文引用数不少于 3，因此 h 指数为 3。