LeetCode 275. H-Index II    原题链接    中等

作者： 作者的头像   yxc ,  2018-06-24 01:32:05 ,  所有人可见 ,  阅读 3851

9


4

题目描述

给定一个科研工作者的一系列论文的引用次数（引用次数是非负整数），已经从小到大排好序，请计算他的h因子。

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

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

进一步：

  • 这道题目是 LeetCode 274. H-Index的升级版，citations 保证是严格递增的；
  • 你能否给出时间复杂度是 $O(logn)$ 级别的算法？

样例

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

算法

(二分) $O(logn)$

由于数组是从小到大排好序的，所以我们的任务是：
在数组中找一个最大的 $h$，使得后 $h$ 个数大于等于 $h$。

我们发现：如果 $h$ 满足，则小于 $h$ 的数都满足；如果 $h$ 不满足，则大于 $h$ 的数都不满足。所以具有二分性质。
直接二分即可。

时间复杂度分析：二分检索，只遍历 $logn$ 个元素，所以时间复杂度是 $O(logn)$。

C++ 代码

class Solution {
public:
    int hIndex(vector<int>& citations) {
        if (citations.empty()) return 0;
        int l = 0, r = citations.size() - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (citations.size() - mid <= citations[mid]) r = mid;
            else l = mid + 1;
        }
        if (citations.size() - l <= citations[l]) return citations.size() - l;
        return 0;
    }
};

11 评论

用户头像
Komorebi_29   2020-12-17 16:36         踩      回复

这样写不用特判

class Solution {
public:
    int hIndex(vector<int>& citations) {
        if(!citations.size()) return 0;
        int l = 0, r = citations.size();
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(citations[citations.size() - mid] >= mid) l = mid;
            else r = mid - 1;
        }
        return r;
    }
};
用户头像
sysml   2019-09-28 11:54         踩      回复

请问这道题目使用第二个模板怎么做？

用户头像
yxc   2019-09-28 21:44         踩      回复

上面题解里是二分出最小的l，满足citations.size() - l <= citations[l])。如果用第二个模板，就先二分出最大的l, 满足citations.size() - l > citations[l]，然后在加一。

用户头像
阿靳   2019-08-18 20:37         踩      回复

看了录播，那个判断条件还是不太懂,为什么是nums[n-mid]>=mid。因为之前说性质的时候说的是h-1满足该性质，我以为是左半区间是符合要求的，但是最后取的是右半区间。

用户头像
yxc   2019-08-18 22:37         踩      回复

如果nums[nums.size() - mid] >= mid 说明至少有 mid 篇文章的引用次数大于等于 mid，说明 $h$ 因子至少是 mid，因此最终答案应该在右区间中寻找。

用户头像
nihaotian   2019-07-16 23:08         踩      回复

为什么这里用不同的模板差别那么大啊，还有最后的特判没看懂

用户头像
extrovert   2019-07-21 14:23         踩      回复

这里用的模板是https://www.acwing.com/blog/content/31/

特判可以避免全0数组之类的情况

用户头像
GTrepublic   2019-07-22 13:54    回复了 extrovert 的评论         踩      回复

全0数组的反例你们第一遍就能想得到吗，我要wa了才知道

用户头像
yxc   2019-07-24 10:18    回复了 GTrepublic 的评论         踩      回复

有些边界确实比较难考虑到，尽力而为吧

用户头像
sysml   2019-04-16 20:55         踩      回复 
// check逻辑：引用数目要大于合格的文章数目
    // 在满足check逻辑的条件下，解在左区间(右面都满足，解肯定在左面)，所以动右边界r=mid
    // 然后相应写出：l=mid-1 和 int mid=(l+r)/2;
    int hIndex(vector<int>& citations) {
        if(citations.size()==0) return 0;
        int n=citations.size();
        int l=0,r=n-1;
        while(l<r){
            int mid=(l+r)/2;
            if(citations[mid]>=n-mid)  r=mid;
            else l=mid+1;
        }
        if(citations[l]>=n-l) return n-l;
        return 0;
    }

请问我的思路对吗？ @yxc

用户头像
yxc   2019-04-17 20:21         踩      回复

对滴