【Day 38 】2022-12-08 - 278. 第一个错误的版本

[azl397985856]

278. 第一个错误的版本

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/first-bad-version

前置知识

• 二分法

  题目描述

  
  你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

[luhaoling]

Idea

使用二分，利用判断左边界的方法，如果是错误的版本，则有右边界减一；如果是正确的版本，则左边界加一

Code

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left=0,right=n;
        while(left<right){
            int mid=(right-left)/2+left;
            if(isBadVersion(mid)){
                right=mid;
            }else
                left=mid+1;
        }
        return left;
    }
}

Complex

Time:O(logn)
Space:O(1)

[tiandao043]

思路

二分

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l=1,r=n;
        while(l<r){
            int mid=l+(r-l)/2;
            if(isBadVersion(mid))r=mid;
            else{l=mid+1;}
        }
        return l;
    }
};

O(logn) O(1)

[steven72574]

思路：二分法

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        return BinarySerach(n);
    }

    public int BinarySerach(int n){
        int start = 1 , end = n;
        while( start + 1 < end){
            int mid = start + (end - start) / 2;
            if(!isBadVersion(mid) ){
                start = mid;
            }else{
                end = mid;
            }

        }
        if(isBadVersion(start)) return start;

        if(isBadVersion(end)) return end;

        return -1;
    }
}

time O(logn) space O(1)

[FlipN9]

// TC: O(logn) O(1)
class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = N;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

[zjsuper]

class Solution: def firstBadVersion(self, n: int) -> int: l,r = 1,n while l<=r: mid = (l+r)//2 if isBadVersion(mid): if mid==1 or not isBadVersion(mid-1): return mid else: r = mid -1 else: l = mid+1

    return l

[arinzz]

class Solution { public: int firstBadVersion(int n) { if(isBadVersion(1)) return 1; long long left=1,right=n,mid; while(left<=right){ mid=(left+right)/2; if(isBadVersion(mid)&&!isBadVersion(mid-1)) return mid; else if(!isBadVersion(mid)) left=mid+1; else right=mid-1; } return n; } };

[Abby-xu]

思路

binary search

代码

class Solution:
    def firstBadVersion(self, n: int) -> int:
        if n == 1 and isBadVersion(n): return n
        l, r = 1, n
        while l <= r:
            mid = int((l+r)/2)
            if isBadVersion(mid):
                if not isBadVersion(mid - 1):
                    return int(mid)
                r = mid - 1
            else:
                l = mid + 1

复杂度

O(logn) / O(1)

[StaringWhere]

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (hi > lo) {
            int mid = lo + ((hi - lo) >> 1);
            if (isBadVersion(mid)) hi = mid;
            else lo = mid + 1;
        }
        return hi;
    }
};

[testplm]

class Solution(object):
    def firstBadVersion(self, n):
        r = n-1
        l = 0
        while(l<=r):
            mid = l + (r-l)/2
            if isBadVersion(mid)==False:
                l = mid+1
            else:
                r = mid-1
        return l

[wtdcai]

代码

class Solution:
    def firstBadVersion(self, n: int) -> int:
        l = 0
        r = n
        while l <= r:
            mid = (l+r) //2
            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

复杂度分析

O(logx)
O(1)

[JancerWu]

/* 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, right = n; 
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}

[buer1121]

class Solution: def firstBadVersion(self, n: int) -> int:

寻找左边界

    left=1
    right=n
    while left<=right:
        mid=(left+right)//2
        if isBadVersion(mid):
            right=mid-1
        else:
            left=mid+1

    return left

[mayloveless]

思路

二分查找，如果是badversion，再往小试探，直到不是badversion，则最近的那个就是最早的

代码

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let low = 0;
        let high = n;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            const midV = isBadVersion(mid);
            if (midV) {
               high = mid - 1
            } else {
               low = mid + 1
            }
        }
        return low;
    };
};

复杂度

时间O(logn) 空间O（1）

[bookyue]

code

    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid))
                right = mid;
            else
                left = mid + 1;
        }

        return left;
    }

[chiehw]

基本思路：

• 二分

大致步骤：

1. 当 left 小于等于 right。
2. 如果 mid 版本是错误的，那么 right 往左移动到 mid-1，否则 left 向右移动到 mid+1；
3. 返回 left。

代码：

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(isBadVersion(mid)){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
};

复杂度分析：

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

[chenming-cao]

解题思路

二分法，寻找最左边的满足条件的值。因为题目中说一定有满足条件的值出现，所有可以省去检查边界的部分。

代码

/* 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 l = 1, r = n;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (isBadVersion(mid)) r = mid - 1;
            else l = mid + 1;
        }
        return l;        
    }
}

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

[yuxiangdev]

public class Solution extends VersionControl { public int firstBadVersion(int n) { int l = 1, r = n; while (l <= r) { int mid = l + (r - l) / 2; if (isBadVersion(mid)) r = mid - 1; else l = mid + 1; } return l;
} }

[Elsa-zhang]

'''278. 第一个错误的版本
'''

class Solution:
    def firstBadVersion(self, n: int):
        l, r = 1, n
        while l<=r:
            mid = (l+r)//2
            if isBadVersion(mid):
                r = mid-1
            else:
                l = mid+1
        return l

[ringo1597]

代码

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;
    }
}

[guowei0223]

典型的二分法

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 0
        right = n
        while left <= right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid -1
            else:
                left = mid + 1
        return left

TC O(logn) SC O(1)

[zywang0]

class Solution {
public:
    int firstBadVersion(int n) {
        int l=1,r=n;
        while(l<r){
            int mid=l+(r-l)/2;
            if(isBadVersion(mid))r=mid;
            else{l=mid+1;}
        }
        return l;
    }
}

[darwintk]

思路

用二分法寻找

代码

class Solution:
    def firstBadVersion(self, n: int) -> int:
        if n==1 and isBadVersion(n): return n
        left = 0
        right = n
        while (left<=right):
            mid = (left+right)//2
            if isBadVersion(mid):
                right = mid-1
            else:
                left = mid+1
        return left

复杂度

时间复杂度 O(logn) 空间复杂度 O(1)

[A-pricity]

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 0
        let right = n
        let mid = Math.floor(n/2)
        while(1){
            if(isBadVersion(mid)==true){
                right = mid
                mid = Math.floor(mid/2)
            }else if(isBadVersion(mid)==false){
                left = mid
                mid = mid + Math.floor((right-mid)/2)
            } 
            if(isBadVersion(left)==true&&isBadVersion(left-1)==false) return left
            if(isBadVersion(right)==true&&isBadVersion(right-1)==false) return right
            if(isBadVersion(mid)==true&&isBadVersion(mid-1)==false) return mid

        }
    };
};

[Alyenor]

var solution = function(isBadVersion: any) {

    return function(n: number): number {
        let l=0,r=n
        while(l<r){
            let mid=((r + l + 1) / 2) | 0
            if(!isBadVersion(mid)) l=mid
            else r=mid-1
        }
        return isBadVersion(l) ? l : l+1

    };
};

[RestlessBreeze]

思路

二分查找

代码

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { 
            int mid = left + (right - left) / 2; 
            if (isBadVersion(mid)) {
                right = mid; 
            } else {
                left = mid + 1; 
            }
        }
        return left;
    }
};

复杂度

时间:o(logn) 空间:o(1)

[AtaraxyAdong]

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;
    }
}

[klspta]

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 0;
        int right = n;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

[GG925407590]

class Solution {
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;
    }
};

[BruceZhang-utf-8]

public class Solution extends VersionControl { public int firstBadVersion(int n) { int left=1; int right=n; while(left<=right){ int mid=left+(right-left)/2; if(isBadVersion(mid)){ right=mid-1; }else{ left=mid+1; } } return left; } }

[liuajingliu]

解题思路

二分法寻找最左边界

代码实现

javaScript

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let low = 0;
        let high = n;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            const midV = isBadVersion(mid);
            if (midV) {
               high = mid - 1
            } else {
               low = mid + 1
            }
        }
        return low;
    };
};

复杂度分析

• 时间复杂度: $O(logn)$
• 空间复杂度: $O(1)$

[paopaohua]

/* 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, right = n;
        while(left < right){
            int mid  = left + (right - left) /2;
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

[Alexno1no2]

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:

        l, r = 1, n

        while l < r:
            mid = l + r >> 1
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1

        return l

[tzuikuo]

思路

二分法

代码

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1,right=n,c;
        while(left<right){
            c=left+(right-left)/2;
            if(isBadVersion(c)){
                right=c;
            }
            else{
                left=c+1;
            }
        }
        return left;
    }
};

复杂度分析

• 时间复杂度：O(log_2(N))
• 空间复杂度：O(1)

[Jetery]

思路

二分

代码 (cpp)

class Solution {
public:
    int firstBadVersion(int n) {
        long l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

[xuanaxuan]

思路

最左二分直接套模板

代码

var solution = function (isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function (n) {
        let left = 0;
        let right = n;
        while (left <= right) {
            const mid = Math.floor(left + (right - left) / 2);
            if (isBadVersion(mid))
                // 收缩右边界
                right = mid - 1;
            // 收缩左边界
            else left = mid + 1;
        }
        return left;
    };
};

复杂度

• 时间复杂度：O(log N)
• 空间复杂度：O(1)

[ggmybro]

public int firstBadVersion(int n) {
        if(isBadVersion(1)){
            return 1;
        }
        int left = 1;
        int right = n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(mid == left){
                break;
            }
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid;
            }
        }
        return right;
    }

[snmyj]

class Solution {
public:
    int firstBadVersion(int n) {
        int low = 1, high = n, mid; 
        while(low < high) {
            mid = low + ((high - low)>> 1);
            if(isBadVersion(mid)) high = mid;
            else low = mid + 1;    
        }
        return low;  
    }
};

[neado]

代码

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (isBadVersion(m)) {
                r = m -1;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
}

[Frederickfan]

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left=0,right=n;
        while(left<right){
            int mid=(right-left)/2+left;
            if(isBadVersion(mid)){
                right=mid;
            }else
                left=mid+1;
        }
        return left;
    }
}

[whoam-challenge]

class Solution: def firstBadVersion(self, n: int) -> int: i, j = 1, n while i <= j: m = (i + j) // 2 if isBadVersion(m): j = m - 1 else: i = m + 1 return i

[sclihuiming]

func firstBadVersion(n int) int {
    left := 1
    right := n

    for left <= right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}