LeetCode——274. H 指数(Java)

2021/7/11 14:06:31

本文主要是介绍LeetCode——274. H 指数(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

题干:
给定一位研究者论文被引用次数的数组(被引用次数是非负整数)。
编写一个方法,计算出研究者的 h 指数。
h 指数的定义:h 代表“高引用次数”(high citations),
一名科研人员的 h 指数是指他(她)的 (N 篇论文中)总共有 h 篇论文分别被引用了至少 h 次。
且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。

例如:某人的 h 指数是 20,这表示他已发表的论文中,每篇被引用了至少 20 次的论文总共有 20 篇。

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

题解思路

首先了解h指数的定义,关键就是找到h这个边界的数字

根据定义我们发现这个h指数可以从排序的倒序开始迭代寻找,这就是简单排序的思路

排序后从后往前,遇到引用的数字大于统计的个数即可返回

这里也可以采用排序统计的方法,其实就是增加一个统计数组来统计应用的次数的个数

最后和简单排序一样,从比较引用数变成比较引用数字的统计

正确代码

    // 简单排序
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int result = 0;
        for (int i = citations.length - 1; i >= 0; i--) {
            if (citations[i] > result) {
                result++;
            }
        }
        return result;
    }

    // 排序记数
    public int hIndex1(int[] citations) {
        int length = citations.length;
        int[] counter = new int[length + 1];
        for (int i = 0; i < length; i++) {
            if (citations[i] >= length) {
                counter[length]++;
            } else {
                counter[citations[i]]++;
            }
        }
        int total = 0;
        for (int i = length; i > 0; i--) {
            total += counter[i];
            if (total >= i) {
                return i;
            }
        }
        return 0;
    }

总结

这里排序统计方法因为每次只是便利统计数组,所以把复杂度控制在O(n)

所以复杂度更胜一筹,而就算法思路而言,第一种方法比较好理解

如果文章存在问题或者有更好的题解,欢迎评论区斧正和评论,各自努力,你我最高处见


这篇关于LeetCode——274. H 指数(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程