Python O(logn) solution


  • 1
    L
    class Solution:
        # @param num, a list of integer
        # @return an integer
        def findMin(self, num):
            left, right = 0, len(num) - 1
    
            while (right - left) > 1:
                mid = (left + right) >> 1
                if num[mid] > num[left] and num[mid] > num[right]:
                    left = mid
                elif num[mid] == num[left]:  #we can get AC of it's previous question if we remove this condition
                    left += 1
                else:
                    right = mid
    
            return min(num[left], num[right])

  • 1
    D

    The solution is O(n). For example, the input is [1,1,1,.......1]
    each time you can only move left by one step


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.