Facebook 面试题:第一个错误的代码版本

代码库的版本号是从 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;
    }
}

更多题解参考

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注