LeetCode 刷题 278- 简单 - 第一个错误版本

ベ布小禅

关注

发布于: 1 小时前

前言

算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！

第一遍，不求最优解，但求能过！！！

📢 这是我刷第 6/100 道力扣简单题

一、题目描述

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

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

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

难度：简单

二、实例


   输入：n = 1, bad = 1   输出：1

复制代码

三、题目解析

首先想到的肯定是暴力循环，一个一个遍历

遍历从 1-n，符合要求立马停止循环，返回当前值

不过他题目要求是尽可能少的调用 API

也就是说，暴力循环肯定是不行的

不过，我才管他行不行，我先试试暴力循环

毕竟我也只会暴力循环

# 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        """        ans = 0  # 设置一个变量接收答案        for i in range(n):            if isBadVersion(i+1):  # 因为i从0开始，到n-1结束                ans = i+1                break        return ans

复制代码

当我提交后，却出了红色，显示超出时间限制，也就是程序运行时间太长了

我不由得陷入了沉思，看来只能换个办法了，但是以我当前的知识储备好像也没别的方法了

我就瞄了一眼题解，发现需要使用二分查找法

3.1 二分查找法是什么

二分查找法是一种算法

他经常用在：

给定一个升序的数组/列表和一个目标值，尽可能快的查找其中的目标值
若存在，返回目标值得索引
若不存在，返回-1
这样的场景

因为是升序的，所以我们可以以数组中间的元素为中线，将数组分为左右两个数组

target = 7  # 给一个目标值start = 0  # 用于计算中间值，和后面陆续的将数组划分为两个数组end = len(li)-1 # 用于计算中间值，记录列表最后值的索引li = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]while start<n:    # 记录一个循环    mid = (start+n)//2  # 值为4    """    一个升序数组/列表    以中间mid（//是保持中间值为整数）为界限    看似分成两个数组    li_left = [1， 2， 3 ，4， 5]    li_right = [6, 7, 8, 9, 10]    """  if target>li[mid]:        # 如果目标值比中间值大，就说名目标值（7）在右边的列表        start = mid+1 # 让start变成右边列表的第一个元素的索引        # 抛弃左边的列表不要，只看右边的列表li_right = [6, 7, 8, 9, 10]    else:        # 如果目标值小于等于中间值，就说明目标值在左边的列表        n = mid # 让n变成左边列表的最大值的索引        # 抛弃右边的列表不要，只看左边的列表

复制代码

随着循环的进行，列表会越来越小，最后只剩目标值，然后最小值的索引 start 就是我们需要的值

3.2 将二分查找法应用在本题

因为我们有了一个接口可以判断哪个是错的，所以我们可以将 bad 看成目标值，将 n（题干）看成列表的最大索引值 n（实例代码），将isBadVerson()看成target>li[mid]

四、代码

# 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        """        start = 0 # 定义一个最小值索引        while start<n:  # 循环            mid = int((start+n)/2) # 计算中间值的索引            if isBadVersion(mid):  # 判断相当于target>li[mid]                # 如果为True，就说明目标值（bad）在左边，相当于目标值比中间值大                n=mid             else:                start=mid+1        return start

复制代码

结语

坚持最重要，每日一题必不可少！

发布于: 1 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/c8789bfab31a1065c8a3ca5f1】。文章转载请联系作者。

ベ布小禅

关注

还未添加个人签名 2021.04.06 加入

平平无奇一萌新，默默无闻学IT，我是布小禅，一个网络专业却对编程及其感兴趣的小白！目前在学python和Java，都很浅显，平时爱写点学习笔记。IT技术交流群：1039347613 也可以联系本人企鹅：2228660752 v：Smly0413

发布

暂无评论

创作场景

LeetCode 刷题 278- 简单 - 第一个错误版本

前言

一、题目描述

二、实例

三、题目解析

3.1 二分查找法是什么

3.2 将二分查找法应用在本题

四、代码

结语

ベ布小禅

评论