[Leetcode] First Bad Version 第一个错误版本

senntyou 发布于2019-08-14 12:33 / 882人阅读

摘要：二分搜索法复杂度时间空间思路因为一个版本是错误，其后面的所有版本都是错误的，所以我们可以用二分搜索，当取中点时，如果中点是错误版本，说明后面都是错误的，那第一个错误版本肯定在前面。如果中点不是错误版本，说明第一个错误版本肯定在后面。

First Bad Version

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.

二分搜索法 复杂度

时间 O(logN) 空间 O(1)

思路

因为一个版本是错误，其后面的所有版本都是错误的，所以我们可以用二分搜索，当取中点时，如果中点是错误版本，说明后面都是错误的，那第一个错误版本肯定在前面。如果中点不是错误版本，说明第一个错误版本肯定在后面。

注意

这里直接使用min <= max的二分模板，因为我们其实要找的是好和坏的分界点，即这个点既不是好也不是坏，所以是找不到的，按照模板的特点，最后退出循环时，max指向小于目标的点，min指向大于目标的点，这里第一个坏的version较大，所以返回min

代码

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int min = 1, max = n, mid = 0;
        while(min <= max){
            mid = min + (max - min) / 2;
            if(isBadVersion(mid)){
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

GPU云服务器云服务器 version版本号第一个数据第一个顶级域名 php第一个字符

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64555.html

【刷算法】LeetCode.278-第一个错误的版本

摘要：不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有个版本，你想找出导致之后所有版本出错的第一个错误的版本。示例给定，并且是第一个错误的版本。题目描述你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有...

JerryC 2019-08-23 11:38 评论0 收藏0
[LeetCode/LintCode] First Bad Version

摘要：分析最后一次循环的时刻当与相差小于时，总是那么如果是，下一次直接跳出循环，返回当与相差大于时，是，变成，如果是，循环结束的条件将是循环结束，返回 Problem The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case,...

lowett 2019-08-15 15:46 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0