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.
Solution 1: Use a count array, count[i] to store the number of papers has i citations. Then iterate the count array from end to start, calculate the sum which is the num of patter with more than i citations. if sum>=i, i is what we want to return.
public class Solution {
public int hIndex(int[] citations) {
int n=citations.length;
int[] count=new int[n+1];
for (int num: citations) {
if (num>=n) count[n]++;
else count[num]++;
}
int total=0;
for (int i=n; i>0; i--) {
total+=count[i];
if (total>=i) return i;
}
return 0;
}
}
没有评论:
发表评论