274

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."
这道题比较容易的办法是直接排序，然后从后往前找，找到n篇引用大于n的就返回n。
但是这样排序至少需要O(nlogn)的时间复杂度。
还有一种办法，使用额外的一个数组记录每种引用数的文章有多少篇，引用数最多记到文章数，因为H-index不可能超过文章数。

var hIndex = function(citations) {
    var stats = [];
    var n = citations.length;
    // 统计各个引用次数对应多少篇文章
    for(let i = 0; i < n; i++){
        let index = citations[i] <= n ? citations[i] : n;
        stats[index] === undefined ? 
        stats[index] = 1:
        stats[index] += 1;
    }
    var sum = 0;
    // 找出最大的H指数
    for(let i = n; i > 0; i--){
        // 引用大于等于i次的文章数量，等于引用大于等于i+1次的文章数量，加上引用等于i次的文章数量 
        sum += stats[i]===undefined ? 0 :stats[i];
        // 如果引用大于等于i次的文章数量，大于引用次数i，说明是H指数
        if(sum >= i){
            return i;
        }
    }
    return 0;
}

275

这个问题在前面问题的基础上，给了一个有序的数组，那就从后往前，或二分查找。

var hIndex = function(citations) {
    // var num = citations.length;
    // var count = 0;
    // for (let i = num - 1;i >= 0;i--) {
    //     count++;
    //     if (citations[i]===count)
    //         return count;
    //     else if (citations[i]<count)
    //         return --count;
    // }
    // return num;
    var l = 0;
    var r = citations.length-1;
    var num = citations.length;
    while (l<=r) {
        var mid = parseInt(l + (r - l) / 2);
        var count = num - mid;
        if (citations[mid]===count)
            return count;
        else if (citations[mid]<count)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return num - r - 1;
};