您现在的位置是：主页 > news > 德州网站推广/网站排名优化多少钱
德州网站推广/网站排名优化多少钱
admin2025/5/9 7:33:44【news】
简介德州网站推广,网站排名优化多少钱,吕邵苍设计公司网站,政府网站信息内容建设报告代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口…
德州网站推广,网站排名优化多少钱,吕邵苍设计公司网站,政府网站信息内容建设报告代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口…
代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。
在线评测地址：LintCode 领扣
样例
n = 5: isBadVersion(3) -> falseisBadVersion(5) -> trueisBadVersion(4) -> true
因此可以确定第四个版本是第一个错误版本。算法：二分
假设第k个版本为第一个错误版本，那么1---n个版本分为1---k-1为正确版本，k---n为错误版本，
我们需要以尽量少的次数去找到这个k，显然我们如果一个个找过去的平均复杂度是O(n)
那么我们可以考虑用二分来找到这个k,二分的复杂度为O(logn)
- 二分[1,n]这个区间
- 判断isBadVersion（mid）
- 如果为false 说明第一个错误版本在mid的右边，令 left = mid
- 反之则在mid左边，令 right = mid
- 缩小判断范围，当left+1>=right的时候结束二分
- 最后再次判断下isBadVersion（left）,如果是错误版本的话返回left,反之返回right.
复杂度分析
- 时间复杂度O(logn)
- 二分的时间复杂度
- 空间复杂度O(1)
- 无需额外空间
public class Solution {/**
* @param n: An integer
* @return: An integer which is the first bad version.
*/public int findFirstBadVersion(int n) {int left = 1, right = n; // 左右边界
while (left + 1 < right){int mid = left + (right - left) / 2;// 判断mid是否为正确版本，如果是的话，那么说明错误版本在mid的右边，反之则在左边
if (SVNRepo.isBadVersion(mid)){right = mid; // 向[left，mid]查找错误版本
}else { left = mid; // 向[mid，right]查找错误版本
}}// 最后判断下left是否是错误版本
if (SVNRepo.isBadVersion(left)){return left;}return right;}
}更多题解参考：九章算法
