LeetCode: 278. 第一个错误的版本(二分查找)
程序员文章站
2022-07-12 09:07:09
...
【问题描述】
你是产品经理,目前正在带领一个团队开发新的产品。
不幸的是,你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
【思路:】
读完题目,就想到了用二分查找的思想来解决。
这个没什么问题,但在做的过程中,我尝试了递归和循环两种解决方法,全部都无法通过最大的那组数据,显示超出时间限制,让我陷入惆怅。
点开评论发现,int mid = low + (high - low) / 2;
这句话是关键啊,绝大多数人都没有注意到
求平均值的时候,(high + low) / 2 这种直接求法会导致数字溢出的危险,所以改用以上那种写法求mid值。这一下才顺利通过!
迭代版本:
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
/*
很难过的那组测试数据
1420736637
1150769282
*/
public int firstBadVersion(int n) {
int i = 1;int j = n;
while(i < j){
int mid = i + (j - i) / 2;
boolean jud = isBadVersion(mid);
if(jud){
j = mid;
}else{
i = mid + 1;
}
}
return i;
}
}
递归版本:
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
/*
1420736637
1150769282
*/
HashMap<Integer, Boolean> hash = new HashMap<Integer, Boolean>();
//分治思想,递归
public int firstBadVersion(int n) {
//参数为区间
return recursion(1, n);
}
public int recursion(int start, int end){
if(start == end){
return start;
}else{
int mid = start + (end - start) / 2;
boolean jud = true;
//如果mid已经查过了,就不需要再次递归了
if(hash.containsKey(mid)){
jud = hash.get(mid);
}else{
jud = isBadVersion(mid);
hash.put(mid, jud);
}
//如果是true,那么false肯定在前半部分
if(jud){
return recursion(start, mid);
}else{
return recursion(mid + 1, end);
}
}
}
}
上一篇: 矩阵乘法