第一个错误的版本
难度:
标签:
题目描述
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4 输出：4 解释：调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1 输出：1
提示：
1 <= bad <= n <= 231 - 1
代码结果
运行时间: 19 ms, 内存: 16.0 MB
/*
* Problem Statement:
* Given n versions [1, 2, ..., n], find the first bad version
* which caused all the following versions to be bad.
* You are given an API bool isBadVersion(version) to check.
* Implement a function to minimize the number of API calls.
*
* Approach:
* Using Java Streams, we can simulate the binary search by generating
* a stream of version numbers and filtering until we find the first
* bad version. However, Java Streams are not ideal for binary search
* and the usage here is more educational.
*/
import java.util.stream.IntStream;
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
return IntStream.rangeClosed(1, n)
.parallel()
.filter(this::isBadVersion)
.findFirst()
.orElse(-1); // In case no bad version is found, though problem guarantees at least one.
}
private boolean isBadVersion(int version) {
// Assume this method is implemented in VersionControl class.
return super.isBadVersion(version);
}
}解释
方法:
这个题解使用二分查找的思路来寻找第一个错误的版本。首先设定左右边界 i 和 j，分别指向版本范围的首尾。然后进入一个循环，每次取左右边界的中点 mid，调用 isBadVersion API 判断第 mid 个版本是否有错。如果有错，说明第一个错误的版本在 mid 的左边，缩小右边界 j 到 mid-1；如果没错，说明第一个错误的版本在 mid 的右边，缩小左边界 i 到 mid+1。当左右边界重合时，i 指向的就是第一个错误的版本，返回 i 即可。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在二分查找中，为什么在发现`mid`版本是错误的之后，你选择将右边界`j`设置为`mid-1`而不是`mid`？
▷🦆
在这个算法实现中，当`i`和`j`相邻时，具体的迭代过程是怎样的？能否详细描述这种边界情况的处理？
▷🦆
在某些编程语言或环境中，`(i + j) // 2`可能导致整数溢出。这个问题在Python中会发生吗？如果会，如何避免？
▷🦆
这种二分查找方法是否能确保找到的是第一个错误的版本，而不仅仅是某个错误的版本？如何验证？
▷相关问题
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
猜数字大小
猜数字游戏的规则如下：
- 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
- -1：我选出的数字比你猜的数字小
pick < num - 1：我选出的数字比你猜的数字大
pick > num - 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！
pick == num
返回我选出的数字。
示例 1：
输入：n = 10, pick = 6 输出：6
示例 2：
输入：n = 1, pick = 1 输出：1
示例 3：
输入：n = 2, pick = 1 输出：1
示例 4：
输入：n = 2, pick = 2 输出：2
提示：
1 <= n <= 231 - 11 <= pick <= n