275. H 指数 II–Leetcode_二分

• 2022 年 8 月 19 日
• 笔记
• 二分算法, 算法, 算法--二分应用

来源：力扣（LeetCode）
链接：//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