Skip to content

Instantly share code, notes, and snippets.

@qiaoxu123
Last active March 13, 2019 00:48
Show Gist options
  • Save qiaoxu123/027e39a8f74f76708ee81e77e671c763 to your computer and use it in GitHub Desktop.
Save qiaoxu123/027e39a8f74f76708ee81e77e671c763 to your computer and use it in GitHub Desktop.
> 排序查找类问题。 最简单的方法是使用暴力查找,从0开始找,找到第一个值为true的数即可。但是这样效率太低。于是尝试用查找方法 二分查找是最常用的查找方式,在这需要注意的是判断初始值是否为true,此时第一个产品为假,则后续判断无效。
//Runtime: 4 ms, faster than 100.00%
//Memory Usage: 8.2 MB, less than 17.32%
class Solution {
public:
int firstBadVersion(int n) {
long begin = 1;
long end = n;
long temp;
if(isBadVersion(1)) return 1;
while(1){
temp = (begin + end)/2;
if(temp == begin)
return end;
if(isBadVersion(temp))
end = temp;
else
begin = temp;
// cout << "begin = " << begin << " " << "end = " << end << endl;
}
}
};
//Runtime: 7024 ms, faster than 5.27%
//Memory Usage: 8.2 MB, less than 14.96%
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int i = 0;
while(!isBadVersion(i)){
i += 1;
}
return i;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment