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

【Leetcode】【每日一题】【中等】274. H 指数

article 2024/9/20 23:48:14

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/h-index/description/?envType=daily-question&envId=2023-10-29

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 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

h指数

例如h指数为3，则说明：

（1）至少发表了3篇论文——>符合条件（2）的元素个数≥3

（2）每篇论文至少被引用3次——>元素大小≥3

自己的思路

输入数组 citations，先将其排序，根据h指数的定义进行判断。

例如示例1

citations = [3,0,6,1,5]

排序后

citations = [0,1,3,5,6]

（1）≥0的元素有5个，记为<0,5>

（2）≥1的元素有4个，记为<1,4>

（3）≥2的元素有3个，记为<2,3>

（4）≥3的元素有3个，记为<3,3>

=====================（其实到这里就可以中止了，因为key＜value，不符合h指数的定义）

（5）≥4的元素有2个，记为<4,2>

（6）≥5的元素有2个，记为<5,2>

（7）≥6的元素有1个，记为<6,1>

所以解题的重点是如何计算value，这里我使用了一层循环寻找比key大的元素个数。

代码

class Solution {
    public int find(int[] citations, int target) {
        int len = citations.length;
        for (int i = 0; i < len; i++) {
            if (citations[i] >= target) {
                return len - i;
            }
        }
        return 0;
    }

    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int len = citations.length;
        for (int i = 0; i < len + 1; i++) {
            int tmp = find(citations, i);
            if (i > tmp && hashMap.size() >= 1)
                break;
            hashMap.put(i, tmp);
        }
        System.out.println(hashMap);

        Object[] obj = hashMap.keySet().toArray();
        Arrays.sort(obj);
        return (int) obj[obj.length - 1];
    }
}

结果感觉不是很好

力扣官方题解

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/h-index/solutions/869042/h-zhi-shu-by-leetcode-solution-fnhl/?envType=daily-question&envId=2023-10-29只需要知道存在即可，例如排序后的示例1：

citations = [0,1,3,5,6]

假设h为0，从后往前比较，

首先是6＞0，即为存在一篇论文，并且这一篇论文被引用次数＞0，则可以将h设为1；

然后是5＞1，即为存在两篇论文，并且这两篇论文被引用次数＞1，则可以将h设为2（为什么是两篇？因为h还没有到达2，所以现在不可能出现引用次数＜2的论文）；

然后是3＞2，即为存在三篇论文，并且这三篇论文被引用次数＞2，则可以将h设为3；

最后是1＜3，因为要取最大的，所以结束比较

代码

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1; 
        while (i >= 0 && citations[i] > h) {
            h++; 
            i--;
        }
        return h;
    }
}