LeetCode H-Index

· 694 words · 2 minute read
2017年7月
LeetCode

274. H-Index

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.

Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

方法

使用辅助内存，开辟一个新数组，用于记录0-N次引用次数各有几篇文章（引用次数大于N的按照N次计算），即桶排序，桶排序的索引即为引用次数。遍历该数组统计，统计过后，遍历一次统计数组，当total大于等于桶的索引时，即total篇paper的引用次数大于等于引用次数

英语原文：

Then we iterate from the back to the front of the buckets, whenever the total count exceeds the index of the bucket, meaning that we have the index number of papers that have reference greater than or equal to the index. Which will be our h-index result. The reason to scan from the end of the array is that we are looking for the greatest h-index.

桶排序：即根据个数，对每个数出现的次数进行排序。

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0){
            return 0;
        }
        int n = citations.length;
        int[] array = new int[n+1];
        for(int i = 0; i < n; i++){
            if(citations[i] > n){
                array[n]++;
            }else{
                array[citations[i]]++;
            }
        }
        int total = 0;
        for(int i = n; i >= 0; i--){
            total += array[i];
            if(total >= i){
                return i;
            }
        }
        return 0;
    }
}

275.H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

方法

针对有序的问题进行查找除了从头到尾遍历还有就是二分查找

其中length-mid表示在mid位置右边的数，即大于当前mid处文献引用的所有文献个数。citations[mid]表示在mid处文献引用次数。当length-mid == citations[mid]时，表示h个文献的引用次数等于h。 时间复杂度为O(logn)

public class Solution {
    public int hIndex(int[] citations) {
        int left = 0;
        int right = citations.length-1;
        int length = citations.length;
        int mid = 0;
        while(left <= right){
            mid = (left + right) / 2;
            if(length-mid == citations[mid]){
                return citations[mid];
            }else if(length-mid > citations[mid]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return length - left;
    }
}
Share