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

[Fightforcoding]

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

Time: O(LogN)

Space:O(1)

[godkun]

思路

• 二分法

代码

PY实现

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

复杂度分析

时间复杂度：O(logN) 空间复杂度：O(1)

[huizsh]

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

[zjy-debug]

代码

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

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

[sleepydog25]

Approach

using brute force will get TLE Binary search

Algorithm

/* 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;
        int right = n;
         while(left < right){

            //making mid 
            int mid = left + (right - left)/2; 

            if (isBadVersion(mid))
                right = mid;

            // narrow down the searching area
            else
                left = mid +1;
         }
         return right;
    }
}

Complexity

1. Time Complexity: O(logn)
2. Space Complexity:O(1)