【Leetcode】278. First Bad Version总结

哈哈 阅读:358 2022-03-12 16:24:45 评论:0
本文章主要介绍了【Leetcode】278. 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.

题意是有一个数组,某个数之后调用isBadVersion都会返回true,找到这个数的位置。

思路

典型的二分查找,需要注意的是右边界向mid靠拢时不用减一,因为要求返回的是第一个开始变化的位置。

另外,开始使用

mid = (left + right) / 2 

总是会TLE,但是用

mid = left + (right - left) / 2 

就没问题,原因是left+right可能超过了INT_MAX。另外可以使用

mid = (left + right) >>> 1 

这种方式,因为是无符号的右移1位。

挺有意思的一题,以后写二分查找时确定mid一定要谨记。

代码

/** 
 * Author: puyangsky 
 * Date: 17/3/14 
 * Complexity: Time O(logN) Space O(1) 
 * Method: 二分查找 
 */ 
public class L278 { 
    public boolean isBadVersion(int version) { 
        return true; 
    } 
    public int firstBadVersion(int n) { 
        int left = 1, right = n; 
        while (left < right) { 
//            int mid = (left + right) >>> 1; 
            int mid = left + (right - left) / 2; 
            //如果中位数为bad,则中位数右边都为bad 
            if(isBadVersion(mid)) right = mid; 
            else left = mid + 1; 
        } 
        return left; 
    } 
}

标签:加密算法
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
排行榜
关注我们