当前位置：首页 > article >正文

Leetcode H 指数

article 2025/1/18 21:21:32

在这里插入图片描述

算法思想：

这道 H 指数 问题的核心思想是，找出一个最大的整数 h，使得至少有 h 篇论文的引用次数 大于等于 h，同时剩下的论文引用次数 不超过 h。为了实现这个目标，代码采用了以下思路：

1. 排序数组

首先，我们将输入的 citations 数组进行 升序排序。排序后的数组使得我们能够快速判断每篇论文的引用次数与位置的关系。

例如，给定 citations = [3, 0, 6, 1, 5]，排序后变为：[0, 1, 3, 5, 6]。

2. 逐个检查可能的 H 指数

排序后，我们逐个遍历排序后的数组，假设当前的索引为 i，从索引 i 到数组末尾的论文数量可以表示为 h = n - i，其中 n 是论文的总数量。

h 表示至少有 h 篇论文的引用次数大于等于 h。
如果当前论文的引用次数 citations[i] ≥ h，说明从索引 i 开始的论文满足 H 指数的定义。

3. 更新 H 指数

一旦找到了满足条件的 h，说明这是我们当前能够得到的最大 H 指数。我们可以直接返回这个值。

示例：
假设 citations = [0, 1, 3, 5, 6]（已排序）：

对于 i = 2，h = 5 - 2 = 3，此时 citations[2] = 3 ≥ 3，满足 H 指数定义，因此 H 指数 = 3。

4. 时间复杂度分析

排序数组的时间复杂度是 (O(n \log n))。
遍历数组的时间复杂度是 (O(n))。
总体时间复杂度：(O(n \log n))。

代码中的关键步骤总结：

对 citations 数组进行 升序排序。
逐个检查从索引 i 到末尾的论文数量（即 h = n - i）。
如果当前论文的引用次数 citations[i] 大于等于 h，说明满足 H 指数的定义。
返回最大满足条件的 h 值。

思维导图总结：

输入数组 → 排序数组 → 遍历数组，计算每篇论文对应的 h 值 → 
判断引用次数是否满足条件 → 找到最大 H 指数 → 输出结果

代码执行示例

对于输入 citations = [3, 0, 6, 1, 5]：

排序后：[0, 1, 3, 5, 6]。
遍历：
- i = 2 时，h = 3，citations[2] = 3 满足条件。
输出结果：H 指数 = 3。

java solution

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

h = n - i的含义

详细解释 `h = n - i` 的含义

在计算 H 指数 的过程中，h 代表一个数值，表示至少有 h 篇论文的引用次数大于等于 h。那么，这个 h 从哪里来呢？

数组索引和论文数量的关系

假设：

我们已经将引用次数数组 升序排序（例如 citations = [0, 1, 3, 5, 6]）。
数组的长度为 n，也就是一共有 n 篇论文。

当我们遍历排序后的数组时，假设当前遍历到的索引是 i：

数组中 索引 i 及其后面的论文数量 就是 n - i。
为什么？因为从索引 i 到数组的末尾，总共有 n - i 篇论文。

解释 `h = n - i`

在排序后的数组中：

n - i 表示：从索引 i 开始，到数组末尾，一共有多少篇论文。
如果当前索引 i 对应的论文引用次数 citations[i] 大于等于 n - i，就意味着：
- 至少有 n - i 篇论文 的引用次数 大于等于 n - i。

这正好符合 H 指数 的定义：

至少有 h 篇论文，每篇论文的引用次数 ≥ h。

因此，我们可以将 h = n - i 作为当前的候选 H 指数。

结合示例详细理解

假设 citations = [3, 0, 6, 1, 5]，排序后变为：[0, 1, 3, 5, 6]，数组长度 n = 5。

遍历步骤：

索引 i = 0：
- n - i = 5 - 0 = 5 → 这意味着“至少有 5 篇论文”。
- citations[0] = 0 → 论文的引用次数为 0，不满足条件（0 < 5）。
索引 i = 1：
- n - i = 5 - 1 = 4 → 这意味着“至少有 4 篇论文”。
- citations[1] = 1 → 论文的引用次数为 1，不满足条件（1 < 4）。
索引 i = 2：
- n - i = 5 - 2 = 3 → 这意味着“至少有 3 篇论文”。
- citations[2] = 3 → 论文的引用次数为 3，满足条件（3 ≥ 3）。
此时，H 指数可能是 h = 3。
索引 i = 3：
- n - i = 5 - 3 = 2 → 这意味着“至少有 2 篇论文”。
- citations[3] = 5 → 论文的引用次数为 5，满足条件（5 ≥ 2）。
但此时 H 指数为 2，已经小于之前的 h = 3。
索引 i = 4：
- n - i = 5 - 4 = 1 → 这意味着“至少有 1 篇论文”。
- citations[4] = 6 → 论文的引用次数为 6，满足条件（6 ≥ 1）。
H 指数仍然不会超过 3。

总结：

n - i 是当前索引 i 到数组末尾的论文数量。
我们检查当前索引 i 的引用次数 citations[i] 是否 ≥ n - i：
- 如果满足，说明至少有 n - i 篇论文的引用次数大于等于 n - i。
- 这时，我们可以将 n - i 作为候选的 H 指数。
由于数组是升序排序的，第一个满足条件的位置就会给出最大 H 指数。