Last active
March 13, 2019 00:48
-
-
Save qiaoxu123/027e39a8f74f76708ee81e77e671c763 to your computer and use it in GitHub Desktop.
> 排序查找类问题。 最简单的方法是使用暴力查找,从0开始找,找到第一个值为true的数即可。但是这样效率太低。于是尝试用查找方法 二分查找是最常用的查找方式,在这需要注意的是判断初始值是否为true,此时第一个产品为假,则后续判断无效。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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; | |
} | |
} | |
}; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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