这是悦乐书的第200次更新，第210篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第66题（顺位题号是278）。您是产品经理，目前领导团队开发新产品。不幸的是，您产品的最新版本未通过质量检查。由于每个版本都是基于以前的版本开发的，因此坏版本之后的所有版本也是坏的。
假设您有n个版本[1,2，...，n]并且您想找出第一个坏的版本，这会导致以下所有版本都不好。您将获得一个API bool isBadVersion（版本），它将返回版本是否错误。 实现一个函数来查找第一个坏版本。 您应该最小化对API的调用次数。
例如：
给定n = 5，版本= 4是第一个坏版本。
调用isBadVersion（3） - > false
调用isBadVersion（5） - > true
调用isBadVersion（4） - > true
然后4是第一个坏版本。
isBadVersion方法在父类VersionControl中定义。
boolean isBadVersion（int version）;
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
对于从1到n的所有版本中，假设好坏版本的临界是第mid个，那么从1到mid-1都是好版本，在调用isBadVersion方法时总是返回false;从mid到n都是坏版本，调用isBadVersion方法时返回的都是true。
直接使用for循环，指针从1开始，依次调用isBadVersion方法，如果返回true，则返回当前指针所表示的版本，反之返回n，即最后一个版本。
此解法的时间复杂度是O(n)，空间复杂度是O(1)，但是提交后提示超时了，我们需要一个更快的方法。
public int firstBadVersion(int n) {
for (int i = 1; i < n; i++) {
if (isBadVersion(i)) {
return i;
}
}
return n;
}
03 第二种解法
从第一种解法的分析那里，相信你应该可以将此问题再抽象下，就变成数据查找问题了，从一个指定大小的容器中找出具体的某一个值。
如果你玩过猜大小的游戏，那么使用二分法来求解，你一定不陌生。不断使用中间数，向预期的结果逼近。
使用二分法需要注意两点：
在求中间数的时候，如果数据类型选用int，直接使用(1+n)/2，如果n是Integer的最大值，加1后会存在溢出的风险，此时我们可以曲线救国，换一种写法，1 + (n-1)/2，就可以避免这种风险，另外也可以将其换成范围更大的long类型，不过就需要强转了。
如果中间值调用isBadVersion方法时返回false，是不能直接判定临界版本就是mid，因为你无法保证mid的前几位都是好版本，正确的做法是让范围缩小到1到mid，再去求中间值进行判断。
此解法的时间复杂度是O(log(n))，空间复杂度是O(1)。
public int firstBadVersion2(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = (right-left)/2 + left;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
04 第三种解法
这是递归的解法，思路和第二种解法一样。
public int firstBadVersion3(int n) {
if (n == 0) {
return 0;
}
return helper(n, 1, n);
}
public int helper(int n, int start, int end) {
if (start >= end) {
return start;
}
int middle = start + (end - start)/2;
if (isBadVersion(middle)) {
return helper(n, start, middle);
} else {
return helper(n, middle + 1, end);
}
}
05 小结
算法专题目前已连续日更超过一个月，算法题文章66+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论