這是悅樂書的第200次更新，第210篇原創(chuàng)
01 看題和準備
今天介紹的是LeetCode算法題中Easy級別的第66題（順位題號是278）。您是產(chǎn)品經(jīng)理，目前領(lǐng)導團隊開發(fā)新產(chǎn)品。不幸的是，您產(chǎn)品的最新版本未通過質(zhì)量檢查。由于每個版本都是基于以前的版本開發(fā)的，因此壞版本之后的所有版本也是壞的。
假設(shè)您有n個版本[1,2，...，n]并且您想找出第一個壞的版本，這會導致以下所有版本都不好。您將獲得一個API bool isBadVersion（版本），它將返回版本是否錯誤。 實現(xiàn)一個函數(shù)來查找第一個壞版本。 您應(yīng)該最小化對API的調(diào)用次數(shù)。
例如：
給定n = 5，版本= 4是第一個壞版本。
調(diào)用isBadVersion（3） - > false
調(diào)用isBadVersion（5） - > true
調(diào)用isBadVersion（4） - > true
然后4是第一個壞版本。
isBadVersion方法在父類VersionControl中定義。
boolean isBadVersion（int version）;
本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測試。
02 第一種解法
對于從1到n的所有版本中，假設(shè)好壞版本的臨界是第mid個，那么從1到mid-1都是好版本，在調(diào)用isBadVersion方法時總是返回false;從mid到n都是壞版本，調(diào)用isBadVersion方法時返回的都是true。
直接使用for循環(huán)，指針從1開始，依次調(diào)用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 第二種解法
從第一種解法的分析那里，相信你應(yīng)該可以將此問題再抽象下，就變成數(shù)據(jù)查找問題了，從一個指定大小的容器中找出具體的某一個值。
如果你玩過猜大小的游戲，那么使用二分法來求解，你一定不陌生。不斷使用中間數(shù)，向預(yù)期的結(jié)果逼近。
使用二分法需要注意兩點：
在求中間數(shù)的時候，如果數(shù)據(jù)類型選用int，直接使用(1+n)/2，如果n是Integer的最大值，加1后會存在溢出的風險，此時我們可以曲線救國，換一種寫法，1 + (n-1)/2，就可以避免這種風險，另外也可以將其換成范圍更大的long類型，不過就需要強轉(zhuǎn)了。
如果中間值調(diào)用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 小結(jié)
算法專題目前已連續(xù)日更超過一個月，算法題文章66+篇，公眾號對話框回復【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。
以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉(zhuǎn)發(fā)就是對我最大的回報和支持！
