274. H-Index

xiaochao 发布于2019-08-14 14:09 / 1143人阅读

摘要：题目解答满足这个的最大值不会超过数组的因为如果超过了，就不可能有这么多的数。所以就是把所有可能的个至少有个的记下来，然后找出最大的。因为是从后向前扫的，所以当前的就是满足条件的最大数。

题目：
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher"s h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

An easy approach is to sort the array first.
What are the possible values of h-index?
A faster approach is to use extra space.

解答：
满足这个index的最大值不会超过citations数组的len, 因为如果超过了，就不可能有这么多的paper数。所以brute force就是把所有可能的n个paper至少有n个citation的n记下来，然后找出最大的n。
代码：

public int hIndex(int[] citations) {
        int maxHIndex = 0;
        for (int i = citations.length; i >= 0; i--) {
            int citNum = i;
            int count = 0;
            for (int j = 0; j < citations.length; j++) {
                if (citations[j] >= citNum) {
                    count++;
                }
            }
            if (count >= citNum) {
                maxHIndex = Math.max(maxHIndex, citNum);
            }
        }
        
        return maxHIndex;
    }

Follow up是牺牲空间来换取时间，那就用另外一个数组来存当前index存在的文章数，然后从后往前相加，如果满足条件就输出这个最大的index。
举个例子：

citations: 3, 0, 6, 1, 5
arr: 0 1 2 3 4 5
val: 1 1   1   2

那么从后向前扫的时候，记一个count,扫到arr(5)的时候，count=2 < 5, 不满足；扫arr(4),count＝2 < 4, 不满足；扫arr(3), count=2+1=3 == 3, 满足。因为是从后向前扫的，所以当前的index就是满足条件的最大数。
代码：

public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        
        int len = citations.length;
        int[] arr = new int[len + 1];
        for (int i = len - 1; i >= 0; i--) {
            //最大的index也不会大于数组的长度，所以，超过数组长度的citation可以都记在len里
            if (citations[i] > len) {
                arr[len] += 1;
            } else {
                //arr的index就是一篇文章中citation的个数，arr的值就是有这么多citation的文章的个数
                arr[citations[i]] += 1;
            }
        }
        
        int count = 0;
        for (int i = len; i >= 0; i--) {
            count += arr[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }

GPU云服务器云服务器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64838.html

[Leetcode] H-Index H指数

摘要：排序法复杂度时间空间思路先将数组排序，我们就可以知道对于某个引用数，有多少文献的引用数大于这个数。代码排序得到当前的指数数组映射法复杂度时间空间思路也可以不对数组排序，我们额外使用一个大小为的数组。 H-Index I Given an array of citations (each citation is a non-negative integer) of a research...

xumenger 2019-08-14 12:35 评论0 收藏0
H-Index & II

H-Index 题目链接：https://leetcode.com/problems... sort： public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0) return 0; // sort ...

mochixuan 2019-08-14 17:25 评论0 收藏0
轨迹数据压缩算法

摘要：数据问题解压缩结果计算高主要运行结果列表容差计算通过的内容算法点列表第一个点最后一个点容差轨迹结果原始图压缩图数据 P0,107.605,137.329 P1,122.274,169.126 P2,132.559,179.311 P3,153.324,184.276 P4,171.884,174.654 P5,186.408,168.634 P6,196.566,145.204 P7...

TANKING 2019-07-31 11:13 评论0 收藏0
httprunner2.5.7参数化三种方式

摘要：重点以上版本参数化都需要借助进行参数化，需严格缩进格式，不能用控制缩进，只能用空格控制直接引用列表进行参数化引用文件进行参数化借助辅助函数进行参数化定义项目的文件框架建立四个文件夹，分别用来存放接口用例用例集测试数据编写接口脚本在文件下，重点：2.x以上版本参数化都需要借助testsuit...

Jokcy 2021-11-11 16:54 评论0 收藏0
从零开始使用node读取txt处理后导出excel

摘要：安装执行版本号，例如以下语句可以安装几的版本好像在墙内只能找到以前的版本使用可以查看现有的版本，可以支持模糊切换。一直说要好好学习，总结知识什么的。一直觉得没有时间。周一终于提交了论文盲审。决定从今天每周都总结一次自己的所学。希望自己能坚持。任务描述：一个医学系的同学要分析一个叫TCGA的数据库，每个实验文件是txt，格式如下： hsa-miR-1228* 5.185500...

frank_fun 2019-08-20 15:46 评论0 收藏0