LC 278. 第一个错误的版本

题目描述

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

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

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

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

示例 1：

1
2
3
4
5
6
7
8
9
输入：n = 5, bad = 4

输出：4

解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：
1
2
3
输入：n = 1, bad = 1

输出：1

提示：

  • $1 <= bad <= n <= 2^{31} - 1$

二分

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

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

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

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

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

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

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
            int mid = l + (r - l) / 2; 
            if (isBadVersion(mid)) r = mid;    
            else l = mid + 1;
        }
        return r;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2; 
            if (isBadVersion(mid)) r = mid;    
            else l = mid + 1;
        }
        return r;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
class Solution:
    def firstBadVersion(self, n: int) -> int:
        l, r = 1, n
        while l < r:
            mid = l + r >> 1
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1
        return r

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

其他「二分」相关题解

最后

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

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

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

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