275. H 指数 II--Leetcode

来源：力扣（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

巴特西

275. H 指数 II--Leetcode_二分

二分思路

二分h指数代码如下

最终优化如下

最新文章

热门文章