【LeetCode】第一个错误的版本 Java 题解

关注

发布于: 2021 年 06 月 13 日

题目描述

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

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

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

示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false调用 isBadVersion(5) -> true调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/first-bad-version著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这是一个简单题目，题干比较长，需要认真理解题目。
isBadVersion 是系统提供的函数，我们可以直接使用。理解题目之后，可以采用二分查找的方法来解决这个题目。
二分查找是用来在一个有序数组中查找某一元素的算法。在这个题目中，用来查找满足某种条件的最小的值。

AC 代码

/* The isBadVersion API is defined in the parent class VersionControl.      boolean isBadVersion(int version); */
public class Solution extends VersionControl {    public int firstBadVersion(int n) {        int left = 1;        int right = n;        while (left < right) {            int mid = left + (right - left) / 2;            if (isBadVersion(mid)) {                right = mid;            } else {                left = mid + 1;            }        }        return left;          }}

复制代码

总结

上述算法的时间复杂度是 O(log n), 空间复杂度是 O(1)
这个题目和其他算法题目的不同是调用了系统的函数，题意并不难。多见一些题型，可以更快的解决题目。
坚持每日一题，加油！

发布于: 2021 年 06 月 13 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/34a8ee4d6ac14ba43ee88ef95】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】第一个错误的版本 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论