- 本题难度: [Lintcode]Medium/[Leetcode]
Topic: Binary Search
Description
我的代码 for Leetcode(在Lintcode中因为isBadVersion调用太多次无法通过)
# The isBadVersion API is already defined for you.# @param version, an integer# @return a bool# def isBadVersion(version):class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ if isBadVersion(1) is True: return 1 else: if n==1: return 0 l = 2 r = n m = (l+r)//2 while(l<=r): print(l,m,r) t1 = isBadVersion(m-1) t2 = isBadVersion(m) print(t1,t2) if t1 is False and t2 is True: print("ok") return m else: if t2 is False: l = m+1 else: if t1 is True: r = m-1 m = (l+r)//2
别人的代码 for Lintcode
#class SVNRepo:# @classmethod# def isBadVersion(cls, id)# # Run unit tests to check whether verison `id` is a bad version# # return true if unit tests passed else false.# You can use SVNRepo.isBadVersion(10) to check whether version 10 is a # bad version.class Solution: """ @param n: An integer @return: An integer which is the first bad version. """ def findFirstBadVersion(self, n): # write your code here r = n-1 l = 0 while(l<=r): mid = l + (r-l)//2 if SVNRepo.isBadVersion(mid)==False: l = mid+1 else: r = mid-1 return l
思路
大思路是二分法,但是我想岔了。
其实无需找到一个自身为true,前一个为false的id,只需要找到最后一个为false的id即可。这样可以减少一次比较。- 时间复杂度: O(log(n))