当前位置:网站首页>【LeetCode-278】第一个错误的版本
【LeetCode-278】第一个错误的版本
2022-08-11 05:30:00 【Ring*】
10.3 第一个错误的版本【278】
10.3.1 题目描述
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
10.3.2 方法一:二分查找
思路及算法
因为题目要求尽量减少调用检查接口的次数,所以不能对每个版本都调用检查接口,而是应该将调用检查接口的次数降到最低。
注意到一个性质:当一个版本为正确版本,则该版本之前的所有版本均为正确版本;当一个版本为错误版本,则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。
具体地,将左右边界分别初始化为 1 和 n,其中 n 是给定的版本数量。设定左右边界之后,每次我们都依据左右边界找到其中间的版本,检查其是否为正确版本。如果该版本为正确版本,那么第一个错误的版本必然位于该版本的右侧,我们缩紧左边界;否则第一个错误的版本必然位于该版本及该版本的左侧,我们缩紧右边界。
这样我们每判断一次都可以缩紧一次边界,而每次缩紧时两边界距离将变为原来的一半,因此我们至多只需要缩紧 O(logn) 次。
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
// 循环直至区间左右端点相同
int mid = left + (right - left) / 2; // 防止计算时溢出
if (isBadVersion(mid)) {
right = mid; // 答案在区间 [left, mid] 中
} else {
left = mid + 1; // 答案在区间 [mid+1, right] 中
}
}
// 此时有 left == right,区间缩为一个点,即为答案
return left;
}
}
复杂度分析
- 时间复杂度:O(logn),其中 n 是给定版本的数量。
- 空间复杂度:O(1)。我们只需要常数的空间保存若干变量。
10.3.3 my answer—二分查找
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
int mid = 0;
while(left < right){
mid = left + (right - left) / 2;
if(isBadVersion(mid)){
right = mid;
}else {
left = mid + 1;
}
}
return left;
}
}
边栏推荐
- 【无标题】
- Day 75
- 第六届蓝帽杯 EscapeShellcode
- JS事件循环机制
- Day 73
- 解决AttributeError: ‘NoneType‘ object has no attribute ‘val‘ if left.val!=right.val:Line 17 问题
- Matplotlib找不到字体,打印乱码
- 精彩联动 | OpenMLDB Pulsar Connector原理和实操
- swagger错误:WARN i.s.m.p.AbstractSerializableParameter - [getExample,421] - Illegal DefaultValue null
- Day 69
猜你喜欢
2022DASCTF X SU 三月春季挑战赛 checkin ROPgadget进阶使用
精彩联动 | OpenMLDB Pulsar Connector原理和实操
JS小技巧,让你编码效率杠杠的,快乐摸鱼
Scene-driven feature calculation method OpenMLDB, efficient implementation of "calculate first use"
Thesis unscramble TransFG: A Transformer Architecture for Fine - grained Recognition
He Kaiming's new work ViTDET: target detection field, subverting the concept of layered backbone
Day 75
本地服务配置内网穿透实现微信公众号整合
Day 77
Asis2016 books null off by one
随机推荐
swagger常用注释API @ApiModel、@ApiModelProperty的用法
Tinker接入全流程---编译篇
手把手导入企业项目(快速完成本地项目配置)
Simple mine sweeping in C language (with source code)
【无标题】
USB URB
Thesis unscramble TransFG: A Transformer Architecture for Fine - grained Recognition
2021-09-11 C language variables and memory allocation
The official website of OpenMLDB is upgraded, and the mysterious contributor map will take you to advance quickly
Matplotlib找不到字体,打印乱码
Day 82
PAT乙级刷题之路
第一章 Verilog语言和Vivado初步使用
mk file introduction
Interpretation of the paper: GAN and detection network multi-task/SOD-MTGAN: Small Object Detection via Multi-Task Generative Adversarial Network
helm安装
c语言-数据存储部分
Invalid revision: 3.18.1-g262b901-dirty
OpenMLDB Meetup No.2 会议纪要
C-自定义类型(结构体、枚举、联合)