题目描述
给定一个科研工作者的一系列论文的引用次数(引用次数是非负整数),请计算他的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;
}
};
请问这道题目使用第二个模板怎么做呢(当我们将区间[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; }
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); } };
另外以后这类问题最好放到问答页面里,这样曝光度高,被回答的概率大