LeetCode:H-Index、H-Index II - H指数

原创
2015/09/10 23:33
阅读数 4.3K

1、题目名称

H-Index(H指数)

2、题目地址

https://leetcode.com/problems/h-index/

3、题目内容

英文: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.

中文:给出一个数组记录一个研究者各篇文章的引用数,写一个函数计算这个研究者的H指数

4、解题方法

H指数是一个2005年由Jorge E. Hirsch提出的用于评估研究人员的学术产出数量与学术产出水平的指标。更详细的信息可以参考h-index的维基百科页面。实现H指数的计算方法可以从它的定义入手,即一个人在其所有学术文章中有N篇论文分别被引用了至少N次,他的H指数就是N。

一段实现此方法的Java代码如下:

/**
 * 功能说明:LeetCode 275 - H-Index
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月10日
 */
public class Solution {
    
    /**
     * 求文献引用的H指数
     * @param citations 引用次数
     * @return H指数
     */
    public int hIndex(int[] citations) {
        
        if (citations.length == 0) {
            return 0;
        }

        //数组元素降序排列
        int temp;
        for (int i = 0; i < citations.length; i++) {
            for (int j = i + 1; j < citations.length; j++) {
                if (citations[i] < citations[j]) {
                    temp = citations[i];
                    citations[i] = citations[j];
                    citations[j] = temp;
                }
            }
        }
        
        //计算H指数
        int result = 0;
        for (Integer cites : citations) {
            if (result >= cites) {
                return result;
            }
            result++;
        }
        
        return result;
    }
}

使用Arrays.sort函数进行排序可以加快计算速度,不过Arrays.sort排序后是升序,所以要用反方向遍历数组:

import java.util.Arrays;

/**
 * 功能说明:LeetCode 275 - H-Index
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月10日
 */
public class Solution {
    
    /**
     * 求文献引用的H指数
     * @param citations 引用次数
     * @return H指数
     */
    public int hIndex(int[] citations) {
        
        if (citations.length == 0) {
            return 0;
        }

        //数组元素降序排列
        Arrays.sort(citations);
        
        //计算H指数
        int result = 0;
        for (int i = citations.length - 1; i >= 0; i--) {
            if (result >= citations[i]) {
                return result;
            }
            result++;
        }
        
        return result;
    }
}

如果数组很长,在排序完毕后也可以试着采用二分查找法计算H指数。

4、275题解题方法

第275题名称:H-Index II(H指数-2)

第275题地址:https://leetcode.com/problems/h-index-ii/

第275题的内容与第274题基本一致,只是多提供了一个条件:传入的数组是升序排列的。这道题仍然可以使用上面的方法计算H指数,不过可以省略对数组进行手工排序的步骤。

import java.util.Arrays;

/**
 * 功能说明:LeetCode 275 - H-Index
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月10日
 */
public class Solution {
    
    /**
     * 求文献引用的H指数
     * @param citations 引用次数
     * @return H指数
     */
    public int hIndex(int[] citations) {
        
        if (citations.length == 0) {
            return 0;
        }

        //计算H指数
        int result = 0;
        for (int i = citations.length - 1; i >= 0; i--) {
            if (result >= citations[i]) {
                return result;
            }
            result++;
        }
        
        return result;
    }
}

END

展开阅读全文
打赏
0
3 收藏
分享
加载中
更多评论
打赏
0 评论
3 收藏
0
分享
返回顶部
顶部