274. H-Index 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.”

Example:

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] 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, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index. 274. H-Index

---

给定一个研究人员的n篇文章及其引用数，求该研究人员的H-index。
一个人的H-index为h说明他有h篇引用数至少为h的论文，比如例子中[3,0,6,1,5]的H-index为3，指他有3篇引用数至少为3的文章，即引用数为3,6,5的3篇文章。
求解方法也不难，先对所有引用数按从大到小排序，然后从大到小累加文章数目，直到引用数小于文章数时停止。代码如下：

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        sort(citations.begin(), citations.end(), std::greater<int>());
        int h = 1;
        while (h <= citations.size()) {
            if (citations[h – 1] < h)
                return h – 1;
            ++h;
        }
        return h – 1;
    }
};

本代码提交AC，用时3MS。 还有一种方法是，不排序，使用Hash。先求出最大引用数，然后把相同引用数的文章Hash到同一个位置。最后从引用数大的开始遍历，累加文章数，直到文章数大于引用数时停止。 此时的返回值需要注意，是较大的h-index，即max(h – hash, c)。比如[2,3,3,3]，则hash[3]=3,hash[2]=1，当遍历到2时，发现不满足，此时的最大h-index是h-hash=4-1=3。 但是如果[2,3,2]，则hash[3]=1,hash[2]=2，当遍历到2时，也发现不满足，但此时并不需要完全回退到3，还可以拿一篇2引用的文章，即最大的h-index是c=2。
代码如下：

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        int maxC = -1, n = citations.size();
        if (n == 0)
            return 0;
        for (int i = 0; i < n; ++i)
            maxC = max(maxC, citations[i]);
        vector<int> hash(maxC + 1, 0);
        for (int i = 0; i < n; ++i)
            ++hash[citations[i]];
        int c = maxC, h = hash[maxC];
        while (c >= h) {
            –c;
            h += hash[c];
        }
        return max(h – hash[c], c);
    }
};

本代码提交AC，用时3MS。