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.
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.
这道题让我们计算一个科研人员的H指数，所谓H指数就是一个人在其所有学术文章中有N篇论文分别被引用了至少N次，他的H指数就是N。
定义比较简单，维基百科提供了一种很简单的算法:
- 将其发表的所有SCI论文按被引次数从高到低排序；
- 从前往后查找排序后的列表，直到某篇论文的序号大于该论文被引次数。所得序号减一即为H指数。
根据上面的算法可以很容易写出正确的程序，代码如下:
/*solution1 as the definition ,4ms*/
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty())
return 0;
sort(citations.begin(),citations.end(),greater<int>());
for(int i=0;i<citations.size();i++){
if(i>=citations[i])
return i;
}
return citations.size();
}
};
在查看了其他人的讨论后，我又获得了一种新的思路，即数组映射法，可以去掉排序的过程。
首先对数组进行遍历，用一个新数组记录引用次数相同的文章数目，这里需要注意的是，如果某篇文章引用次数超过了数组长度n，则将这个引用次数看成n即可，因为H指数不可能超过数组长度，之后，我们从次数i等于n的文章开始，统计次数大于等于i的文章数目之和，因为大于等于i的文章数目等于次数大于等于i+1的文章数目加上次数等于i的文章数目。
如果计算出文章数目之和大于等于引用次数i的值，则说明该引用次数的值即为H指数。
代码如下:
/*solution2 */
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty())
return 0;
int size=citations.size(),sum=0;
vector<int> count(size+1,0);
/*统计引用次数为i的文章数目*/
for(int i=0;i<size;i++)
count[citations[i]>size?size:citations[i]]++;
for(int i=size;i>=0;i--){
/*从最后一个开始，引用次数大于等于i的文章数目是引用次数大于等于i+1的文章数加上引用次数等于i的文章数目*/
sum+=count[i];
if(sum>=i)
return i;
}
return -1;
}
};
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。