原标题:LeetCode初级算法--排序和搜索01:第一个错误的版本
原文来自:博客园 原文链接:https://www.cnblogs.com/aimi-cn/p/11740667.html
一、引子
这是由LeetCode官方推出的的经典面试题目清单~
这个模块对应的是探索的初级算法~旨在帮助入门算法。我们第一遍刷的是leetcode推荐的题目。
查看完整的剑指Offer算法题解析请点击github链接:
github地址
二、题目
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
1、思路
首先我们可以想到的就是把整个列表都顺序遍历一遍,第一次调用接口出现False的下一个为True的就是我们要求的值,但是这个算法会超时。
我们使用二分查找:
我们要寻找第一个错误版本,也就是要保留最后一个false之后的第一个true。所以在更新边界的时候,右边界就不用减1了,这样最后当左右相等时一定是第一个true。
2、编程实现
python
# The isBadVersion API is already defined for you.
# @param version, an integer# @return a bool
# def isBadVersion(version):class Solution: def firstBadVersion(self, n): """
:type n: int
:rtype: int
"""
left = 1
right = n
while left<right:
mid = left + (right-left)//2
if isBadVersion(mid):
right = mid
else:
left = mid+1
return left
本文由博客一文多发平台 OpenWrite 发布!
免责声明:本文来自互联网新闻客户端自媒体,不代表本网的观点和立场。
合作及投稿邮箱:E-mail:editor@tusaishared.com