题目描述
给定一个科研工作者的一系列论文的引用次数（引用次数是非负整数），已经从小到大排好序，请计算他的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;
}
};
这样写不用特判
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; } };请问这道题目使用第二个模板怎么做？
上面题解里是二分出最小的
l，满足citations.size() - l <= citations[l])。如果用第二个模板，就先二分出最大的l, 满足citations.size() - l > citations[l]，然后在加一。看了录播，那个判断条件还是不太懂,为什么是nums[n-mid]>=mid。因为之前说性质的时候说的是h-1满足该性质，我以为是左半区间是符合要求的，但是最后取的是右半区间。
如果
nums[nums.size() - mid] >= mid说明至少有mid篇文章的引用次数大于等于mid，说明 h 因子至少是mid，因此最终答案应该在右区间中寻找。为什么这里用不同的模板差别那么大啊，还有最后的特判没看懂
这里用的模板是https://www.acwing.com/blog/content/31/
特判可以避免全0数组之类的情况
全0数组的反例你们第一遍就能想得到吗，我要wa了才知道
有些边界确实比较难考虑到，尽力而为吧
// 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
对滴