【Day 38 】2024-05-15 - 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 是第一个错误的版本。

[xy147]

js代码

var solution = function (isBadVersion) {
  return function (n) {
    let left = 1;
    let right = n;

    while (left <= right) {
      let mid = Math.floor((right + left) / 2);

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

    return left;
  };
};

复杂度分析

时间复杂度：O(logN)

空间复杂度：O(1)

[Lizhao-Liu]

func firstBadVersion(_ n: Int) -> Int {
    var left = 1
    var right = n
    while left <= right {
        var mid = left + (right - left) / 2
        if isBadVersion(mid) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

[xil324]

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

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

[Martina001]

简单二分查找 时间复杂度 logn 空间复杂度 o(1) class Solution { public: int firstBadVersion(int n) { int left = 1; int right = n;

    int ans = -1;
    while (left <= right) {
        int mid = (right-left)/2 + left;
        if (isBadVersion(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return ans;
}

};

[smallppgirl]

思路： 二分法

代码

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

        if isBadVersion(left):
            return left
        else:
            return right

时间复杂: O(log(n)) 空间复杂: O(1)

[GReyQT]

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        int left = 0, right = n,mid;
        while ( left <right) 
        {
            mid = left + (right -left)/2;
            if(isBadVersion(mid)) 
                right = mid;
            else
                left = mid+1;
        }
        return left;
    }
};

[CathyShang]

二分

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

• Time O(logn)
• Space O(1)

[hillsonziqiu]

思路

二分法

代码

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

        return l;
    };
};

复杂度分析

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

[Dtjk]

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

[zhiyuanpeng]

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    # def firstBadVersion(self, n):
    #     """
    #     :type n: int
    #     :rtype: int
    #     """
    #     l, r = 1, n
    #     while l < r:
    #         mid = (l+r)//2
    #         # if find B, G is right
    #         if isBadVersion(mid):
    #             r = mid - 1
    #         # if find G, we want to find the right most G, current may be the right most, so l = mid
    #         if not isBadVersion(mid):
    #             l = mid
    #     return l+1

        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            """
            l, r = 1, n
            while l < r:
                mid = (l+r)//2
                # if find B, G is right
                if isBadVersion(mid):
                    r = mid
                # if find G, we want to find the right most G, current may be the right most, so l = mid
                if not isBadVersion(mid):
                    l = mid + 1
            return l