成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] First Bad Version 第一個錯誤版本

senntyou / 960人閱讀

摘要：二分搜索法復(fù)雜度時間空間思路因為一個版本是錯誤，其后面的所有版本都是錯誤的，所以我們可以用二分搜索，當(dāng)取中點時，如果中點是錯誤版本，說明后面都是錯誤的，那第一個錯誤版本肯定在前面。如果中點不是錯誤版本，說明第一個錯誤版本肯定在后面。

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.
二分搜索法 復(fù)雜度

時間 O(logN) 空間 O(1)

思路

因為一個版本是錯誤，其后面的所有版本都是錯誤的，所以我們可以用二分搜索，當(dāng)取中點時，如果中點是錯誤版本，說明后面都是錯誤的，那第一個錯誤版本肯定在前面。如果中點不是錯誤版本，說明第一個錯誤版本肯定在后面。

注意

這里直接使用min <= max的二分模板，因為我們其實要找的是好和壞的分界點，即這個點既不是好也不是壞，所以是找不到的，按照模板的特點，最后退出循環(huán)時，max指向小于目標(biāo)的點，min指向大于目標(biāo)的點，這里第一個壞的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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64555.html

相關(guān)文章

  • 【刷算法】LeetCode.278-第一個錯誤的版本

    摘要：不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測。由于每個版本都是基于之前的版本開發(fā)的，所以錯誤的版本之后的所有版本都是錯的。假設(shè)你有個版本，你想找出導(dǎo)致之后所有版本出錯的第一個錯誤的版本。示例給定，并且是第一個錯誤的版本。 題目描述 你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個團隊開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測。由于每個版本都是基于之前的版本開發(fā)的，所以錯誤的版本之后的所有...

    JerryC 評論0 收藏0

  • [LeetCode/LintCode] First Bad Version

    摘要：分析最后一次循環(huán)的時刻當(dāng)與相差小于時，總是那么如果是，下一次直接跳出循環(huán)，返回當(dāng)與相差大于時，是，變成，如果是，循環(huán)結(jié)束的條件將是循環(huán)結(jié)束，返回 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 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • LeetCode 精選TOP面試題【51 ~ 100】

    摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復(fù)雜度為 ...

    Clect 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<