題目

  • 題目連結
  • 目標函式 : firstBadVersion(n)
    • Input : n: int
    • Output : int

解題概念

  • 題意 : 題目會給予一 function isBadVersion(version)，會回傳該 version 是否為 Bad version
    • version 為 1 ~ n
    • 只要 first bad version 出現，後續 verison 皆為 bad
  • 此題須回傳 first bad version 為何

我的寫法

  • 想法 : 採用遞迴的方式
    • 可以把 Version 表示成 [false, false, false ... true, true.... true]
    • 因此可以用 Binary Search 的方式去搜尋
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def firstBadVersion(self, n):
        
        left = 1
        right = n

        if n == 1 : return 1

        while left <= right:
            mid = (left + right) // 2

            if not isBadVersion(mid) : # Version mid 為 false
                left = mid + 1  # 往右搜尋
            else: # Version mid 為 true
                right = mid - 1 # 往左搜尋
        
        return left
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(\log(n))}$
    • Runtime: 10 ms (faster than 91.45%)
    • Memory Usage: 13.3 MB (more than 32.90%)

解答 or 其他優秀寫法

  • 想法 : 寫法與我類似，但有學到在取兩數中間值不要使用 mid = (left + right) // 2
    • 因為 left 與 right 有可能為 INT_MAX，兩數會導致 Overflow 的問題發生
    • 因此，可改採用 mid = left + (right - left) // 2 的寫法
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def firstBadVersion(self, n):
        
        left = 1
        right = n

        if n == 1 : return 1

        while left <= right:
            mid = left + (right - left) // 2

            if not isBadVersion(mid) :
                left = mid + 1
            else:
                right = mid - 1
        
        return left
  • 成效 :
    • Runtime: 13 ms (faster than 79.87%)
    • Memory Usage: 13.1 MB (more than 95.56%)