H-Index Series

发表于

H-Index

Question

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.

Analysis

采用类似于桶排序的方法

  • count长度为数组长度len+1，用于记录不同引用次数的文章个数
  • 引用次数大于等于len：count[len]++; 其余则是对应引用次数下标的位置++
  • 从count最后一个元素开始遍历并加至hindex，当hindex>=i时，代表已经至少有i篇文章的引用次数至少为i了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int hIndex(int[] citations) {
        int size=citations.length;
        int[] count=new int[size+1];
        
        for(int item:citations){
            if(item>=size)
                count[size]++;
            else
                count[item]++;
        }
        
        int hindex=0;
        for(int i=size;i>=0;i--){
            hindex+=count[i];
            if(hindex>=i)
                return i;
        }
        return 0;
    }
}

H-Index II

Question

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

Hint:

  1. Expected runtime complexity is in O(log n) and the input is sorted.

Analysis

https://discuss.leetcode.com/topic/23399/standard-binary-search

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int hIndex(int[] citations) {
        int start=0;
        int len=citations.length;
        int end=len-1;
        while(start<=end){
            int mid=(start+end)/2;
            if(citations[mid]==len-mid) return citations[mid];
            else if(citations[mid]<len-mid) start=mid+1;
            else end=mid-1;
        }
        return len-(end+1);
    }
}