来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/h-index-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目的大意是这样的
有一个升序排列的数组citations，返回citations的h指数
h指数:在数组citations中，至少有h个元素，他们的值大于等于h
提示：如果h有多种可能的值h指数是其中最大的那个。
二分思路
二分h指数
简要证明h指数具有二分性质
如果数组citations不存在一个h指数i，那么一定不会存在一个h指数i+1,i+2,...,i+k(k>=1)
举个例子
假设在一组递增序列中，没有两个大于等于2的元素，那么大于等于3的元素最多只会有一个
由此得出h指数具有二分性质
二分h指数代码如下
class Solution {
public:
bool check(int h,vector<int>& citations){
int len = -1;
for(int i=0;i<citations.size();i++){
if(citations[i]>=h && citations.size()-i == h){
// 得到有len-i+1篇论文至少引用了h次
len = citations.size()-i;
break;
}
}
if(len!=-1)return 1;
else return 0;
}
int hIndex(vector<int>& citations) {
int l=1,r=citations.size(),mid;
while(l<r){
mid = (l+r+1)/2;
if(check(mid,citations))l=mid;
else r=mid-1;
}
if(check(l,citations))return l;
else return 0;
}
};
因为数组citations是单调递增的，所以check函数也可以用二分优化
最终优化如下
class Solution {
public:
bool check(int h,vector<int>& citations){
int l=0,r=citations.size()-1,mid;
while(l<r){
mid = (l+r)/2;
if(citations[mid]>=h)r=mid;
else l=mid+1;
}
if(citations[l]>=h && citations.size()-l>=h)return 1;
else return 0;
}
int hIndex(vector<int>& citations) {
int l=1,r=citations.size(),mid;
while(l<r){
mid = (l+r+1)/2;
if(check(mid,citations))l=mid;
else r=mid-1;
}
if(check(l,citations))return l;
else return 0;
}
};
这里需要注意一点，如果citations.size()-l>=h说明一定有h个元素大于等于h
