LC 278. 第一个错误的版本

题目描述

这是 LeetCode 上的 278. 第一个错误的版本 ，难度为 简单。

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

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

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

示例:

1
2
3
4
5
6
7
给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。 

二分

一道交互题，根据题意可知，是尽可能少调用 isBadVersion 方法来找到分割点。

考虑存在「没有错误版本」和「全是错误版本」的情况，但如果往头部插入一个正确版本，往尾部插入一个错误版本作为哨兵，仍然具有「二段性」。

实际上，只需要进行这样的思考即可，不需要真正插入这样的哨兵，把这个哨兵逻辑放到最后返回的时候判断一下即可。

那么只需要将 isBadVersion 当做 check 函数进行二分即可。

二分通常有以下两种写法，分别代表「找到最靠近中心的 True」 和「找到最靠近中心的 False」。

另外根据数据范围需要注意计算 mid 时的爆 int 问题，可以通过使用类似 l + (r - l) / 2 的做法解决，也可以通过一个临时 long 来解决。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            long tmp = (long)l + r >> 1;
            int mid = (int)tmp;
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            long tmp = (long)l + r + 1 >> 1;
            int mid = (int)tmp;
            if (!isBadVersion(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return !isBadVersion(r) ? r + 1 : r;
    }
}

  • 时间复杂度：$O(\log{n})$
  • 空间复杂度：$O(1)$

其他「二分」相关题解

最后

这是我们「刷穿 LeetCode」系列文章的第 No.278 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。