LeetCode 274. H-Index    原题链接    中等

作者： 作者的头像   yxc ,  2018-06-24 01:19:11 ,  所有人可见 ,  阅读 2781

3


题目描述

给定一个科研工作者的一系列论文的引用次数（引用次数是非负整数），请计算他的h因子。

h因子的定义：一个科学家如果有 $h$ 篇文章的引用次数至少是 $h$，并且其他文章的引用次数不超过 $h$，我们就说他的影响因子是 $h$。

注意： 如果一个人有多个可能的 $h$，返回最大的 $h$ 因子。

样例

输入：所有文章的引用次数 = [3,0,6,1,5]
输出：3 
解释：[3,0,6,1,5] 表示一共有5篇文章，每篇文章分别被引用
      3, 0, 6, 1, 5次。由于共有3篇文章的引用次数大于等于3，
      且其他两篇文章的引用次数不超过3，所以h因子是3。

算法

(线性扫描) $O(nlogn)$

我们要在数组中找一个最大的 $h$，使得有 $h$ 个数大于等于 $h$。

我们可以先将原数组从小到大排序，然后从大到小枚举 $h$，直到数组中后 $h$ 个数大于等于 $h$ 为止。

时间复杂度分析：排序的时间复杂度是 $O(nlogn)$，扫描的时间复杂度是 $O(n)$。所以总时间复杂度是 $O(nlogn)$。

C++ 代码

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int res = 0;
        for (int i = 0; i < citations.size(); i ++ )
            if (citations.size() - i <= citations[i])
            {
                res = citations.size() - i;
                break;
            }
        return res;
    }
};

2 评论

用户头像
sysml   2019-09-28 11:32         踩      回复

请问这道题目使用第二个模板怎么做呢(当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时)？
我的代码没有通过,不知道问题在哪里：

int hIndex(vector<int>& citations) {
        if(citations.size()==0) return 0;
        sort(citations.begin(),citations.end());
        int l=0,r=citations.size()-1;
        while(l<r){
            int mid=l+r+1>>1;   // 找到最后一个 文章数量大于等于数目的
            cout<<citations[mid]<<" "<<citations.size()-mid<<endl;
            if(citations.size()-mid>citations[mid]) l=mid; // [l,mid-1] [mid,r]
            else r=mid-1;
        }
        // return citations[l];
        cout<<l<<": "<<citations[l]<<endl;
        if(citations.size()-l<=citations[l]) return citations.size()-l;
        return 0;
    }
用户头像
yxc   2019-09-28 21:43         踩      回复 
class Solution {
public:
    int hIndex(vector<int>& citations) {
        if(citations.size()==0) return 0;
        sort(citations.begin(),citations.end());
        int l=0,r=citations.size()-1;
        while(l<r){
            int mid=l+r+1>>1;   // 找到最后一个 文章数量大于等于数目的
            if(citations.size()-mid>citations[mid]) l=mid; // [l,mid-1] [mid,r]
            else r=mid-1;
        }
        if (citations.size() - l <= citations[l]) l -- ;
        return citations.size() - (l + 1);
    }
};

另外以后这类问题最好放到问答页面里，这样曝光度高，被回答的概率大