Leetcode May Challenge - 05/01: First Bad Version(Python)

Eliza ·

更新时间:2024-09-20

· 557 次阅读

题目描述

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

例子

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

解释

你在带领一个团队开发一款产品，这个产品有n个版本[1, 2, 3, 4, … , n]，然后在第n个版本的时候你发现版本是有问题的。有一个条件就是如果该产品在某一个版本坏了，那么接下来的所有版本都是坏的。现在你需要找到该产品是从哪个版本开始出的问题。
这里我们是没有办法直接访问产品版本的列表去看好坏的，而是需要一个函数isBadVersion(i)，i为版本号。当你调用这个函数，这个函数会返回true/false，就可以知道这个产品版本的好坏。

思路 思路1：暴力求解

最一目了然的思路肯定是暴力解。我从i = 1开始调用isBadVersion函数，一直到这个函数给我返回True为止。暴力解的最差时间复杂度也显而易见的O(n)。本文不列出暴力解的代码，只要有基础的人应该一分钟之内就可以写出来。

思路2：二分法

我们从n个版本的中间版本开始查找（比如共3个版本，我们就从第二个开始），如果中间版本是好的，说明第一个坏版本在中间版本之后出现，所以后面我们只需要在后面的版本中查找。反之如果中间版本是坏的，则我们需要继续往前查找是否有坏版本出现的更早（我在写代码的时候为了更容易解释，用一个变量记录了当前状态下最先出现的坏版本）。
上述是第一次循环。按照该思路循环下去，知道左右边界交叉为止。此时返回我记录最先出现坏版本的变量即可。

代码

# 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
        """
        #规定左右边界以及记录坏版本的变量（初始值只要不在1...n范围内都可以，不一定必须是-1）。
        left = 1
        right = n
        first_bad_version = -1
        #开始循环
        while left <= right:
            #找到中间版本
            mid = (left + right) // 2
            #如果中间版本是坏的，往左查
            if isBadVersion(mid):
                first_bad_version = mid
                right = mid - 1
            #反之往右查
            else:
                left = mid + 1
        return first_bad_version