X

LEETCODE 278. First Bad Version解题思路分析

题目大意:

第一个错误的版本

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

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

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

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。 

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=278

解题思路分析:

我们最终要求的答案实际上是正确与错误版本的分界线,这非常类似于在一个递增数组中找特定值,对于这类问题,二分查找是最好的方案。初始时,二分的low位于1,high位于n。mid是他们的中间值。如果版本mid是错误版本,那么说明mid之后都是错误版本,我们将范围缩小至low到mid-1范围,反之范围扩大至mid+1到high范围,重复此过程,直到low大于high为止,最终的low即是答案。

这是一道典型而简单的二分查找题目。如果你对二分查找不熟悉,或者你很苦于二分查找的边界问题,建议你参考我之前总结的文章:LEETCODE常见算法之二分查找超详细白话讲解

另外本题还有一个需要注意的地方,由于n会非常大,在计算low+high时可能会超出int范围,因此需要将low与high定义为long型。

实现代码:

public int firstBadVersion(int n) {
    long low=1,high=n;
    while(low<=high){
        int mid=(int)((low+high)/2);
        if(isBadVersion(mid)){
            high=mid-1;
        }else{
            low=mid+1;
        }
    }
    return (int)low;
}

本题解法执行时间为12ms。

Runtime: 12 ms, faster than 98.79% of Java online submissions for First Bad Version.

Memory Usage: 36.1 MB, less than 5.63% of Java online submissions for First Bad Version.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-278-first-bad-version解题思路分析/
Categories: leetcode
kwantong: