LeetCode 275. 在此题中二分两种模板的比较
原题链接
简单
作者:
ChinaPie
,
2019-11-01 17:49:32
,
所有人可见
,
阅读 754
模板一: 需要特判
C++ 代码
class Solution {
public:
int hIndex(vector<int>& citations) {
int l = 0, r = citations.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if(citations[mid] >= citations.size() - mid) r = mid;
else l = mid + 1;
}
if(!citations.empty() && citations[0] == 0 && citations.back() == 0) return 0;
else return citations.size() - l;
// 如果没有元素的话,r是会取到到size() - 1的
// 这样的话citations.size() - l == 1, 只有零才会出现这种极端情况[0],[0,0],[0,0,0]...
// 如果用第二个模板的话,最后r会取到0,这个时候就不用加特殊判断了
}
};
模板二: 不需要特判
// 如上面所说,这个可以很好的避免上一个模板遇到的情况
// 也说明了两个模板在某些问题上的一些差别
class Solution {
public:
int hIndex(vector<int>& citations) {
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;
}
};
这样就不需要特判了