leetcode
leetcode 251 ~ 300
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

代码结果

运行时间: 21 ms, 内存: 16.4 MB


/*
 * 题目思路:
 * 1. 使用Java Stream对引用次数数组进行处理。
 * 2. 先排序,然后通过遍历找出最大的 h 值。
 * 3. 返回最终的 h 值。
 */
import java.util.Arrays;
 
public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        return Arrays.stream(citations) // 转换为Stream
                .sorted() // 对Stream中的元素进行排序
                .map(i -> n - Arrays.binarySearch(citations, i)) // 映射计算h值
                .filter(h -> citations[n - h] >= h) // 过滤出满足条件的h值
                .max() // 找到最大值
                .orElse(0); // 如果没有找到,返回0
    }
}

解释

方法:

该题解的思路是先将引用次数数组按降序排序,然后从前往后遍历。对于每个位置 i,如果该位置的引用次数 citations[i] 大于等于 i+1,说明至少有 i+1 篇论文的引用次数大于等于 i+1,更新结果 res 为 i+1。最终返回 res 即为所求的 h 指数。

时间复杂度:

O(nlogn)

空间复杂度:

O(logn) 或 O(n)

代码细节讲解

🦆
请问为什么在计算h指数时需要将引用次数数组按降序排序?
在计算h指数时,将引用次数数组按降序排序是为了更方便地找到满足条件的最大h值。按照降序排序后,我们可以从左向右检查每篇论文的引用次数是否满足至少有i+1篇论文的引用次数大于等于i+1。这样排序后的数组直接反映了引用次数的顺序,使得算法可以直接通过遍历数组来确定h指数,而不需要额外的数据结构或复杂的计算。
🦆
在判断citations[i] >= i+1时,为什么使用i+1而不是直接使用i作为比较的索引?
在判断citations[i] >= i+1时,使用i+1而不是i是因为数组的索引是从0开始的,而h指数的定义是至少有h篇论文引用次数不少于h。因此,当我们在位置i(从0开始计数)检查时,实际上我们是在检查是否有i+1篇论文满足条件。如果使用i,那么对于位置0(第一篇论文),我们将无法正确地检查是否有至少1篇论文的引用次数大于等于1,从而导致算法错误。
🦆
如果数组中存在重复的引用次数,这种方法是否仍然有效?会不会影响最终计算出的h指数?
即使数组中存在重复的引用次数,该方法仍然有效并且不会影响最终计算出的h指数。算法通过降序排序后,重复的引用次数会连续出现,算法在遍历时会考虑到这些连续的相同值。由于h指数的定义是至少有h篇论文的引用次数不少于h,重复的引用次数只会增加满足条件的论文数量,不会导致h指数计算错误。
🦆
题解中没有考虑citations数组为空的情况,这样是否会在实际应用中引发错误?
如果citations数组为空,按照题解中的逻辑确实会在实际应用中引发错误,因为代码试图对一个空数组进行排序和遍历,这可能导致运行时错误。解决这个问题的方法是在代码开始处加入一个检查,如果数组为空,则直接返回0。这样可以确保算法在处理空数组时的正确性和鲁棒性。

相关问题

H 指数 II

给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数,citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义:h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (n 篇论文中)至少 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

 

示例 1:

输入:citations = [0,1,3,5,6]
输出:3
解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
     由于研究者有3篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3

示例 2:

输入:citations = [1,2,100]
输出:2

 

提示:

  • n == citations.length
  • 1 <= n <= 105
  • 0 <= citations[i] <= 1000
  • citations升序排列