# 1.第一个错误的版本(easy)
TIP
更好的阅读体验应该是:
- 审题-思考
- 答题
- 整理-归纳
# 一、题目
LeetCode:278.第一个错误的版本 (opens new window)
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 isBadVersion(version)
接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
# 二、二分法解题
二分查找是一种基于比较目标值和数组中间元素的教科书式算法。
- 如果目标值等于中间元素,则找到目标值。
- 如果目标值较小,继续在左侧搜索。
- 如果目标值较大,则继续在右侧搜索。
时间复杂度:O(logN)
。
空间复杂度:O(1)
。
# 三、基础模版II
- 确定初始的左右边界:
left
: 0right
: nums.length-1mid
: (left + (right - left) >> 1)
- 查找条件需要访问元素的直接右邻居。
- 使用元素的右邻居来确定是否满足条件,并决定是向左还是向右。
- 保证查找空间在每一步中至少有 2 个元素。
- 需要进行后处理。 当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。
# 四、题解
分析模版
- 我们的目标是:寻找出错的版本
- 如果mid值出错,
证明出错的版本 <= mid
,那么右侧就可以抛弃了 - 如果mid值没出错,
证明出错的版本 > mid
,那么左侧就可以抛弃了
- 如果mid值出错,
看基础模版II,版本判断函数
在帮助我们判断mid值右侧
是否有错误的值。
Javasciprt 代码
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let min = 0;
let max = n;
// 因为mid = mid = max是结束的源头,所以不能相等
while(min < max){
let mid = min + ((max - min) >> 1);
if(isBadVersion(mid)){
// 出错版本,可能是初始版本,所以保留
max = mid;
}else{
min = mid + 1;
}
}
return min;
};
};
如果大家对 min < max 存在疑问,可以看下面的代码
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let min = 0;
let max = n;
let ans;
// 因为mid = mid = max是结束的源头,所以不能相等
while(min <= max){
let mid = min + ((max - min) >> 1);
if(isBadVersion(mid)){
// 出错版本,可能是初始版本,所以保存,同时跳过它
ans = mid;
max = mid - 1; // 注意这里
}else{
min = mid + 1;
}
}
return ans;
};
};
两种解法一样,我们不需要过于纠结~
# 五、写在最后
本文是二分查找-模版II 的第一题,后面的几道题的也算是本模版的微调版,加油~
如果对你有所帮助不妨给本项目的github 点个 star (opens new window),这是对我最大的鼓励
关于我
- 花名:余光
- WX:j565017805
- 沉迷 JS,水平有限,虚心学习中
其他沉淀