力扣经典150题第十一题：H指数

计算研究者的 H 指数

在本文中，我们将讨论如何计算研究者的 H 指数。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

提示：

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

示例

示例 1：

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

输出：3

解释：研究者总共有 5 篇论文，每篇论文分别被引用了 3, 0, 6, 1, 5 次。研究者的 H 指数为 3，因为有 3 篇论文每篇被引用次数至少为 3。

示例 2：

输入：citations = [1, 3, 1]

输出：1

解决方案

排序 + 线性扫描

我们可以通过排序数组 citations 并进行线性扫描来解决该问题：

1. 首先对数组 citations 进行升序排序。
2. 从后向前遍历排序后的数组。对于排序后的数组中第 i 个位置的值 citations[i]，表示至少有 i+1 篇论文被引用了 citations[i] 次。
3. 找到最大的 h 指数，使得至少有 h 篇论文被引用了 h 次。

import java.util.Arrays;

public int hIndex(int[] citations) {
    Arrays.sort(citations);
    int n = citations.length;
    int hIndex = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        int count = n - i;
        if (citations[i] >= count) {
            hIndex = count;
        } else {
            break;
        }
    }
    
    return hIndex;
}

复杂度分析

• 时间复杂度：O(nlogn)，其中 n 是数组 citations 的长度，主要由排序算法的时间复杂度决定。
• 空间复杂度：O(1)，只需要常数级别的额外空间用于存储变量。

测试示例

int[] citations1 = {3, 0, 6, 1, 5};
int[] citations2 = {1, 3, 1};

System.out.println("Test Case 1:");
System.out.println("Expected Result: 3");
System.out.println("Actual Result: " + hIndex(citations1));

System.out.println("Test Case 2:");
System.out.println("Expected Result: 1");
System.out.println("Actual Result: " + hIndex(citations2));

输出结果为：

Test Case 1:
Expected Result: 3
Actual Result: 3

Test Case 2:
Expected Result: 1
Actual Result: 1

总结与展望

通过本篇博客，我们详细讨论了力扣经典150题中的跳跃游戏 II 问题，并提供了贪心算法的实现方法。这种方法具有高效性和简洁性，在实际应用中具有广泛的适用性。

结语

希望本文能够帮助大家更好地理解和掌握跳跃游戏 II 的解题思路和实现方法，欢迎提出您的宝贵意见和建议。