大厂面试真题:第一个错误的代码版本-阿里云开发者社区

开发者社区> 开发与运维> 正文

大厂面试真题:第一个错误的代码版本

简介: 大厂面试真题:第一个错误的代码版本

代码库的版本号是从 1 到 n 的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错,具体接口详情和调用方法请见代码的注释部分。

在线评测地址:领扣刷题官网

样例

n = 5:

    isBadVersion(3) -> false
    isBadVersion(5) -> true
    isBadVersion(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;
    }
}

更多题解参考:九章Solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章